标签：长链 ch 剖分 int 18 Tree son 节点

长链剖分

1.算法简介与性质

长链剖分本质上就是另外一种链剖分方式。

长链剖分与重链剖分有相通之处，后者是将子树大小最大的儿子作为重儿子，前者则是将子树深度最大的儿子作为重儿子。可见两者只是换了一个剖分形式。

长链剖分有如下性质：

性质 1：每个节点所在长链末端为其子树内最深节点。根据定义可知。
性质 2：一个节点的 $k$ 级祖先所在长链长度一定不小于 $k$。
- 设 $x$ 的 $k$ 级祖先为 $y$ （$k$ 级祖先，向上跳 $k$ 到达的祖先），如果 $y$ 所在的长链小于 $k$, 那么它所在的链一定不是长链，显然 $y - x $ 这条链更优。那么 $y $ 所在的重链长度至少为 $k$，性质成立。
性质 3：从根节点到任意叶子节点经过的轻边条数不超过 $\sqrt{n}$，这比重链剖分 $log\ n$ 稍劣一些。
- 如果一个点 $x$ 从一条重链跳到了另外一条重链上，那么跳跃到的这条重链的长度不会小于之前的重链长度。
  那么在最坏的情况下，重链长度分别为 $1,2,3,...,\sqrt{n}$，也就是最多跳跃 $\sqrt{n}$次。

2.应用：树上 $k$ 级祖先

$n\ log\ n$ 倍增预处理求出每个节点 $u$ 的 $2^k$ 级祖先，以及对于每条长链，从长链顶端向上 / 向下 $i$ 步分别能走到哪个节点，其中 i 不大于长链深度。此外，预处理每个数在二进制下的最高位，记为 $h_i$ 。

查询 $(u,k)$ ($u$ 的 $k$ 级祖先)
首先跳到 $u$ 的 $2^{h_k}$ 级祖先 $v$。由于我们预处理了从 $v$ 所在长链顶端 $t$ 向上 / 下走不超过链长步分别到哪个节点，故不难直接查询。综上，时间复杂度为 $O(n\ log\ n)−O(1)$。

P5903 【模板】树上 k 级祖先

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
using namespace std;
const int N = 5e5 + 67;
ui s;
inline ui get(ui x) {
	x ^= x << 13, x ^= x >> 17, x ^= x << 5;
	return s = x; 
}
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, q, rt, lg;
ll ans;
int f[N][20], d[N], son[N], top[N], mxd[N], h[N];
int tot, Head[N], to[N], Next[N];
vector<int> up[N], down[N];
void add(int u, int v){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot;
}
void dfs1(int x){
	d[x] = d[f[x][0]] + 1, mxd[x] = 1;
	for(int i = 1; i <= lg; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; dfs1(y);
		mxd[x] = max(mxd[x], mxd[y] + 1);
		if(mxd[son[x]] < mxd[y]) son[x] = y;
	}
}
void dfs2(int x, int topf){
	if(x == topf) up[x].resize(mxd[x]), down[x].resize(mxd[x]);
	down[topf][d[x] - d[topf]] = x, top[x] = topf;
	if(son[x]) dfs2(son[x], topf);
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == son[x]) continue;
		dfs2(y, y);
	}
}
int main(){
	n = read(), q = read(), s = read(), lg = log2(n);
	for(int i = 1; i <= n; ++i) !(f[i][0] = read()) ? (rt = i, void()) : add(f[i][0], i);
	dfs1(rt), dfs2(rt, rt);
	for(int i = 1; i <= n; ++i){
		if(top[i] != i) continue;
		for(int j = 0, cur = i; j < mxd[i] && cur; ++j, cur = f[cur][0]) up[i][j] = cur;
	}
	for(int i = 1; i <= n; ++i) for(int j = 0; j <= lg; ++j) if(i >> j & 1) h[i] = j;
	for(int i = 1, las = 0; i <= q; ++i){
		int x = (get(s) ^ las) % n + 1, k = (get(s) ^ las) % d[x];
		x = !k ? x : f[x][h[k]], k -= (k == 0 ? 0 : (1 << h[k]));
		int t = top[x];
		if(d[x] - k >= d[t]) las = down[t][d[x] - k - d[t]];
		else las = up[t][d[t] - (d[x] - k)];
		ans ^= 1ll * i * las;
	}
	printf("%lld\n", ans);
	return 0;
}

3. 应用：优化深度相关的 DP

3.1 一般形式

长链剖分的价值主要体现在能优化树上与深度有关的 DP。如果子树内每个深度仅有一个信息，就可以使用长链剖分优化。一般形式如：设 $f_{i,j}$ 表示以 $i$ 为根的子树内，深度为 $j$ 的节点的贡献。

3.2 例题 CF1009F Dominant Indices

我们只关心每个节点子树内深度为 $j$ 的节点个数而非具体是哪些节点，很容易写出转移方程。设 $f_{i,j}$ 表示子树 $i$ 深度为 $j$ 的节点个数，则

\[\large f_{i,j}=\sum\limits_{k \in son(i)} \ f_{k, j - 1} \]

$f_{i,0} = 1$

直接暴力显然会 T 飞。

这时候就要请出我们的长链剖分优化DP 了。

我们可以采用一个优化策略：对于一个节点 $x$，我们先对它的长儿子做 DP，但这里可以使用一些技巧，让长儿子把 dp 出来的东西直接存到 $f_x$ 里面去（当然观察 dp 式可以发现这边需要错一位, 即 $f_{x,i} = f_{son[x], i - 1}$），然后再把其他轻儿子 dp 出来的东西与 $f_u$ 暴力合并。

这里我们详细说一下如何实现这些优化（好多博客都没有讲的很清楚，导致我看了很久，也可能是我太菜了）。

这里我们使用指针为 $f$ 动态申请内存来减少空间消耗。显然空间变成 $O(n)$ 的了。

我们只需要对每一个长链的顶端节点申请内存，具体的，对 $u$ 节点申请内存后，设 $v$ 为它的长儿子，那么 $f_v = f_u + 1$，这样写还有一个好处，就是我们可以直接实现 $f_{x,i} = f_{son[x], i - 1}$ 这一步操作，因为 $v$ 的下标相当于 $u$ 的往前移了一位。

这样时间也能变成 $O(n)$ 了。因为每个节点都只会在它所在的长链顶端被暴力合并一次。

答案的统计就很显然了。注意一点，由于枚举距离的时候没有枚举 $0$ ,所以 $0$ 的情况要特判一下，即$f_{x,ans_u} = 1$ 的时候（子树为一条链）。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, cur;
int buf[N], ans[N], *f[N], mx[N];
int fa[N], d[N], mxd[N], son[N];
int tot, Head[N << 1], Next[N << 1], to[N << 1];
void add(int u, int v){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot;
}
void dfs1(int x, int f){
	d[x] = d[f] + 1, fa[x] = f;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == f) continue;
		dfs1(y, x);
		if(mxd[y] > mxd[son[x]]) son[x] = y;
	}
	mxd[x] = mxd[son[x]] + 1;
}
void dfs2(int x){
	f[x][0] = 1;
	if(son[x]){
		f[son[x]] = f[x] + 1; //共享内存 
		dfs2(son[x]), ans[x] = ans[son[x]] + 1; //从长儿子继承答案 
	} 
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; if(y == fa[x] || y == son[x]) continue;
		f[y] = buf + cur, cur += mxd[y], dfs2(y); //分配内存 
		for(int j = 1; j <= mxd[y]; ++j){
			f[x][j] += f[y][j - 1]; //暴力合并 
			if(f[x][j] > f[x][ans[x]] || (f[x][j] == f[x][ans[x]] && j < ans[x])) ans[x] = j; //更新答案 
		}
	}
	if(f[x][ans[x]] == 1) ans[x] = 0;
}
int main(){
	n = read();
	for(int i = 1; i < n; ++i){
		int u = read(), v = read();
		add(u, v), add(v, u);
	}
	dfs1(1, 0), f[1] = buf, cur += mxd[1], dfs2(1);
	for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
	return 0;
}