简介
长链：点 $u$ 的长链指从 $u$ 出发，到达其深度最深的叶子节点的路径
重儿子：$u$ 在长链上的儿子
性质：
对一棵树进行长链剖分之后，树上所有链的长度之和为 $O(n)$
任意一个点 $u$ 的 $k$ 级祖先所在长链的长度至少为 $k$
证明：
若 $u,v$ 在一条长链上显然
若 $u,v$ 不在一条长链上，说明 $v$ 除了 $u$ 所在的子树以外，存在一棵更深的子树
任意一个节点到根节点经过的轻边最多有 $\sqrt n$ 条
证明：
走第一条轻边的时候，大小至少加了 $1$，第二次就是 $2$，第 $k$ 次大小至少加了 $k$
所以最多走 $\sqrt n$ 条
应用
最广泛的应用是 $O(1)$ 求 $u$ 的 $k$ 级祖先？
首先 $O(n \log n)$ 预处理出倍增表，同时预处理出 $Log$ 数组，$Log[i]$ 表示不超过 $i$ 的最大的二的次幂
同时预处理出每条长链的顶点向上走 $Len$ 步和向下走 $Len$ 步能到的点，其中 $Len$ 表示链长
这里的复杂度是 $O(n) $
现在考虑如何查询，我们直接先跳 $Log[k]$ 步，然后找到这个点所在长链的顶点，判断最终需要到的点是在顶点的上面还是下面，注意到无论是在上面还是在下面，距离都小于 $k$，也就是说一定被预处理到了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
int n, m;
struct Edge {
int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
int dep[maxn], mxd[maxn], son[maxn], f[maxn][21];
void dfs(int u, int fa) {
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dep[v] = dep[u] + 1; mxd[v] = dep[v] = dep[u] + 1;
f[v][0] = u; dfs(v, u);
if (mxd[v] > mxd[son[u]]) son[u] = v;
mxd[u] = max(mxd[u], mxd[v]);
}
}
int top[maxn];
void dfs(int u, int fa, int topf) {
top[u] = topf;
if (son[u]) dfs(son[u], u, topf);
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa || v == son[u]) continue;
dfs(v, u, v);
}
}
int Log[maxn]; vector<int> Up[maxn], Down[maxn];
void init_kfa() { Log[0] = -1;
for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
for (int j = 1; j <= 20; ++j)
for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
for (int u = 1; u <= n; ++u) {
if (top[u] != u) continue; int Len = mxd[u] - dep[u];
for (int i = 0, v = u; i <= Len && v; ++i) Up[u].push_back(v), v = f[v][0];
for (int i = 0, v = u; i <= Len && v; ++i) Down[u].push_back(v), v = son[v];
}
}
inline int query(int u, int k) {
if (k >= dep[u] || !k) return k ? 0 : u;
u = f[u][Log[k]]; k ^= 1 << Log[k];
if (dep[u] - dep[top[u]] >= k)
return Down[top[u]][dep[u] - dep[top[u]] - k];
else return Up[top[u]][k - dep[u] + dep[top[u]]];
}
int lans;
int main() { fill(head, head + maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i < n; ++i) {
int x, y; cin >> x >> y;
add_edge(x, y); add_edge(y, x);
} mxd[1] = dep[1] = 1; dfs(1, 0); dfs(1, 0, 1); init_kfa();
cin >> m;
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y; x ^= lans; y ^= lans;
cout << (lans = query(x, y)) << "\n";
}
return 0;
}给定一棵有根树，选 $k$ 个叶子，使得从根到这些叶子的路径的权值和最大（重复的只算一次
能够发现这个东西每次所贡献的答案就是 长链剖分之后第若干长的链
简要题解：给定一棵 $n$ 个节点的有根树，我们定义 $f_{u,k}$ 为 $u$ 的子树内距离 $u$ 为 $k$ 的点的个数，对于每个节点 $u$ 求 $f_{u,k}$ 最大的 $k$
$n\le 10^6$
简要题解：我们在 $dp$ 的时候先 $dp$ 长儿子，那么将长儿子的 $dp$ 合并到点 $u$ 只需要右移一位，这个可以用指针实现，除了长儿子以外直接暴力即可，时间复杂度为 $O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21int buf[maxn], *now = buf;
int *newbuf(int n) { int *res = now; now += n; return res; }
int *f[maxn], ans[maxn];
void dfs(int u, int fa) {
f[u][0] = 1;
if (son[u]) {
f[son[u]] = f[u] + 1;
dfs(son[u], u);
ans[u] = ans[son[u]] + 1;
}
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa || v == son[u]) continue;
f[v] = newbuf(len[v] + 1); dfs(v, u);
for (int k = 1; k <= len[v] + 1; ++k) {
f[u][k] += f[v][k - 1];
if (f[u][k] > f[u][ans[u]] ||
f[u][k] == f[u][ans[u]] && k < ans[u]) ans[u] = k;
}
} if (f[u][ans[u]] == 1) ans[u] = 0;
}