"蔚来杯"2022牛客暑期多校训练营6 - B. Eezie and Pie题解 (非正解的树链剖分)

Eezie and Pie

原题指路: https://ac.nowcoder.com/acm/contest/33191/B

题意 ($3\mathrm{s}3\backslash \; \backslash mathrm\{s\}$)

给定一棵包含编号$1\sim n1\backslash sim\; n$的$nn$个节点的树,其中根节点为$11$号,每个节点处有外卖站和点外卖的人.节点$i(1\le i\le n)i\backslash \; \backslash \; (1\backslash leq\; i\backslash leq\; n)$处的外卖站只能送节点$ii$到根节点的简单路径上的节点.此外,节点$i(1\le i\le n)i\backslash \; \backslash \; (1\backslash leq\; i\backslash leq\; n)$处的外卖站有一个最长距离$d_{i}d\_i$,表示该外卖站只能送与其距离(经过的边数)不超过$d_{i}d\_i$的节点.对每个节点$i(1\le i\le n)i\backslash \; \backslash \; (1\backslash leq\; i\backslash leq\; n)$,求有多少个外卖站可以给它送外卖.

第一行输入整数$n(1\le n\le 2\mathrm{e}6)n\backslash \; \backslash \; (1\backslash leq\; n\backslash leq\; 2\backslash mathrm\{e\}6)$.接下来$(n-1)(n-1)$行每行输入两个整数$u,v(1\le u,v\le n)u,v\backslash \; \backslash \; (1\backslash leq\; u,v\backslash leq\; n)$,表示节点$uu$与$vv$间存在无向边.数据保证输入的信息构成一棵树.最后一行输入$nn$个整数$d_1,\cdots ,d_n(0\le d_i\le n)d\_1,\backslash cdots,d\_n\backslash \; \backslash \; (0\backslash leq\; d\_i\backslash leq\; n)$.

输出$nn$个整数,其中第$i(1\le i\le n)i\backslash \; \backslash \; (1\backslash leq\; i\backslash leq\; n)$个整数表示对节点$ii$,求有多少个外卖站可以给它送外卖.

思路

对每个节点$uu$,考察它到根节点的简单路径上与其相距$d_{u}d\_u$的节点$vv$(若$uu$到根节点的距离$\le d_u\backslash leq\; d\_u$,则取$vv$为根节点),则$uu$处的外卖站能给$uu$到$vv$的简单路径上的节点(含端点)送外卖,只需给这段路径上的节点的权值都$+1+1$即可.考虑树剖,它可快速实现给两节点间的路径上的节点权值$+1+1$,而线段树可快速实现查询每个节点处的权值,故只需解决对每个节点$uu$,如何快速找到对应的$vv$.

朴素做法,$u=father[u]u=father[u]$回跳$d_{u}d\_u$次(中途跳到根节点可break),最坏的情况是一条链,需回跳$O(n^2)O(n^2)$次,显然TLE.

考虑优化,类似于Manacher算法的优化思路,能跳尽量跳,不能跳再暴力扩展.注意到树剖中$top[u]top[u]$表示节点$uu$所在重链的顶点,则若它们的深度之差$\le d[u]\backslash leq\; d[u]$,则$uu$直接跳到其所在重链的顶点$top[u]top[u]$处,并更新剩余的步数.重复该过程,直至剩下的步数不足以跳到所在重链的顶点或已到达根节点.若此时还有剩下的步数,则暴力$u=father[u]u=father[u]$回跳,直至找到$vv$.过程:设$1,a,b,c1,a,b,c$是一条重链,$cc$的儿子节点是$dd$,而$d,e,f,gd,e,f,g$是一条重链,且$d[g]=6d[g]=6$.首先$gg$花费$33$的步数跳到所在重链的顶点$dd$处,此时剩下$33$个步数.$dd$花费一个步数跳到其父亲节点$cc$处,此时剩下$22$个步数.注意到剩下的步数不足以跳到$cc$所在的重链的顶点$11$处,开始暴力扩展.$cc$先跳到其父亲节点$bb$处,$bb$再跳到其父亲节点$aa$处,此时步数用完,故节点$gg$处的外卖站能给$gg$到$aa$的路径上的节点送外卖.最坏的情况是每个节点剩下的步数都是跳到其所在重链的顶点的步数$-1-1$,则都需暴力扩展,时间复杂度为$O(n^2)O(n^2)$,显然TLE.

考虑进一步优化.设节点$uu$的DFS序为$dfn[u]=vdfn[u]=v$,设$idfn[v]=uidfn[v]=u$.注意到重链上的节点的DFS序连续,则对节点$uu$剩下的步数$tmptmp$不足以跳到所在重链的顶点$top[u]top[u]$的情况,其能跳到的最高节点即DFS序为$dfn[u]-tmpdfn[u]-tmp$的节点,即节点$v=idfn[\max \{1,dfn[u]-tmp\}]v\; =\; idfn[\backslash max\backslash \{1,\; dfn[u]\; -\; tmp\backslash \}]$,其中与$11$取$\max \backslash max$是为了防止$dfn[u]-tmpdfn[u]-tmp$减成非正数.

总时间复杂度$O(n{}^{2}n)O(n\backslash log^2n)$,最坏约$2\mathrm{e}6\times 20^2=8\mathrm{e}82\backslash mathrm\{e\}6\backslash times\; 20^2=8\backslash mathrm\{e\}8$,树剖常数小,牛客的评测机最快$1\mathrm{e}9\mathrm{/}\mathrm{s}1\backslash mathrm\{e\}9/\backslash mathrm\{s\}$,可过.

代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<complex>
#include<array>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
#include<functional>
#include<cassert>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int, int, int> tiii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef queue<pii> qii;
typedef complex<double> cp;
#define umap unordered_map
#define pque priority_queue
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl '\n'
#define npt nullptr
#define so sizeof
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define hashset_finetune(p) (p).reserve(1024); (p).max_load_factor(0.25);  // 哈希表防卡
const double eps = 1e-7;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int dx[4] = { 0,-1,0,1 }, dy[4] = { -1,0,1,0 };
// ----------------------------------------------------------------
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }  // 注意要不要改成ll
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }  // 注意要不要改成ll
int lowbit(int x) { return x & (-x); }
int cmp(double a, double b) {
	if (fabs(a - b) < eps) return 0;
	else if (a > b) return 1;
	else return -1;
}
int sgn(double x) {
	if (fabs(x) < eps) return 0;
	else if (x > 0) return 1;
	else return -1;
}

template<typename T>
void read(T& x) {
	x = 0;
	T sgn = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') sgn = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch & 15);
		ch = getchar();
	}
	x *= sgn;
}

template<typename T>
void write(T x) {
	if (x < 0) {
		putchar('-');
		x *= -1;
	}
	if (x < 10) putchar(x + 48);
	else write(x / 10), putchar(x % 10 + 48);
}

ll qpow(ll a, ll k, ll MOD) {
	ll res = 1;
	while (k) {
		if (k & 1) res = res * a % MOD;
		k >>= 1;
		a = a * a % MOD;
	}
	return res;
}
// ----------------------------------------------------------------

const int MAXN = 2e6 + 6, MAXM = MAXN << 1;
int n;  // 节点数
int d[MAXN];  // 最长距离
int head[MAXN], edge[MAXM], nxt[MAXM], idx;
ll w[MAXN];
int dfn[MAXN], cnt, idfn[MAXN];  // 节点的DFS序,dfn[u]=v,idfn[v]=u
ll neww[MAXN];  // neww[i]表示DFS序为i的节点的权值
int depth[MAXN];  // 节点的深度
int siz[MAXN];  // siz[u]表示以节点u为根节点的子树的大小
int top[MAXN];  // top[u]表示节点u所在的重链的顶点
int father[MAXN];  // 每个节点的父亲节点
int son[MAXN];  // 每个树中节点的重儿子
struct Node {
	int l, r;
	ll lazy;
	ll sum;  // 区间和
}SegT[MAXN << 2];

void add(int a, int b) {
	edge[idx] = b, nxt[idx] = head[a], head[a] = idx++;
}

void dfs1(int u, int fa, int dep) {  // 求树中节点的重儿子:当前节点为u,其父亲节点为fa,u的深度为dep
	depth[u] = dep, father[u] = fa, siz[u] = 1;
	for (int i = head[u]; ~i; i = nxt[i]) {
		int j = edge[i];
		if (j == fa) continue;

		dfs1(j, u, dep + 1);
		siz[u] += siz[j];
		if (siz[son[u]] < siz[j]) son[u] = j;
	}
}

void dfs2(int u, int to) {  // 找到每条重链:当前节点u所在的重链顶点为to
	dfn[u] = ++cnt, idfn[cnt] = u, neww[cnt] = w[u], top[u] = to;
	if (!son[u]) return;  // 叶子节点

	dfs2(son[u], to);  // 优先搜重儿子,重儿子与u在同一条重链上

	for (int i = head[u]; ~i; i = nxt[i]) {  // 搜轻儿子
		int j = edge[i];
		if (j == father[u] || j == son[u]) continue;

		dfs2(j, j);  // 轻儿子是自己所在的重链的顶点
	}
}

void push_up(int u) {
	SegT[u].sum = SegT[u << 1].sum + SegT[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
	SegT[u] = { l,r,0,neww[r] };
	if (l == r) return;

	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	push_up(u);
}

void push_down(int u) {
	auto& root = SegT[u], & left = SegT[u << 1], & right = SegT[u << 1 | 1];
	if (root.lazy) {
		left.lazy += root.lazy, left.sum += root.lazy * (left.r - left.l + 1);
		right.lazy += root.lazy, right.sum += root.lazy * (right.r - right.l + 1);
		root.lazy = 0;
	}
}

void modify(int u, int l, int r, int k) {  // [l,r]+=k
	if (l <= SegT[u].l && r >= SegT[u].r) {
		SegT[u].lazy += k;
		SegT[u].sum += (ll)k * (SegT[u].r - SegT[u].l + 1);
		return;
	}

	push_down(u);
	int mid = SegT[u].l + SegT[u].r >> 1;
	if (l <= mid) modify(u << 1, l, r, k);
	if (r > mid) modify(u << 1 | 1, l, r, k);
	push_up(u);
}

void modify_path(int u, int v, int k) {  // 节点u到v的路径上的节点权值+=k
	while (top[u] != top[v]) {  // 节点u和v不在一条重链上
		if (depth[top[u]] < depth[top[v]]) swap(u, v);  // 保证节点u比v更深
		modify(1, dfn[top[u]], dfn[u], k);
		u = father[top[u]];
	}

	// 节点u和v在同一条重链上
	if (depth[u] < depth[v]) swap(u, v);  // 保证节点u比节点v更深
	modify(1, dfn[v], dfn[u], k);
}

ll query(int u, int l, int r) {
	if (l <= SegT[u].l && r >= SegT[u].r) return SegT[u].sum;

	push_down(u);
	int mid = SegT[u].l + SegT[u].r >> 1;
	ll res = 0;
	if (l <= mid) res += query(u << 1, l, r);
	if (r > mid) res += query(u << 1 | 1, l, r);
	return res;
}

void solve() {
	memset(head, -1, so(head));

	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		add(a, b), add(b, a);
	}

	dfs1(1, -1, 1);  // 从根节点开始搜,根节点无父亲节点,根节点的深度为1
	dfs2(1, 1);  // 从根节点开始搜,根节点所在的重链的顶点是根节点
	build(1, 1, n);

	for (int i = 1; i <= n; i++) cin >> d[i];

	for (int i = 1; i <= n; i++) {
		int u = i;
		int tmp = d[u];
		while (tmp && depth[u] - depth[top[u]] <= tmp) {
			tmp -= depth[u] - depth[top[u]];
			u = top[u];
			if (u == 1 || u == 0) break;
			else if (tmp) {  // 注意防止tmp减成负数
				u = father[u];
				tmp--;
			}
		}
		u = max(1, u);  // 防止u变为0
		if (tmp) u = idfn[max(1, dfn[u] - tmp)];
		modify_path(i, u, 1);
	}

	for (int i = 1; i <= n; i++) cout << query(1, dfn[i], dfn[i]) << ' ';
}

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------	
	// CaseT  // 单测时注释掉该行
		solve();
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

提交记录,只用关流同步的cin,cout,耗时$2204\mathrm{m}\mathrm{s}2204\backslash \; \backslash mathrm\{ms\}$跑得还挺快:

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=53226227