长链剖分
Tangninghaha
·
·
算法·理论
长链剖分类似于树链剖分，但是将划分重儿子的依据由子树大小，变为最深链的深度。
应用
常使用长链剖分优化与深度有关的 DP。
例如，设 f[i][j]，其中 j 最大为 i 子树的深度。此时，用长链剖分后，直接继承重儿子的信息，再暴力合并轻儿子。这样每一个点只会在链顶被合并一次，复杂度是线性的，非常优秀。
CF1009F - Dominant Indices
题意
给定一棵树，定义 f_{u,i} 表示每一个节点 u 的子树内，到 u 距离为 i 的节点数量。求每一个 u 能使得 f_{u,i} 最大的 i，如果有多个 i 满足条件，输出最小的 i。
#### 解法
考虑直接求出 $f_{u,i}$。用指针实现，一条重链上共用一块内存，这样可以保证复杂度，具体参考代码：
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct Graph
{
int head[N], nxt[N << 1], to[N << 1], tot;
void push(int u, int v)
{
nxt[++tot] = head[u];
to[tot] = v;
head[u] = tot;
}
} G;
int fa[N], len[N], wson[N];
void dfs(int u)
{
for (int i = G.head[u]; i; i = G.nxt[i])
{
int v = G.to[i];
if (v == fa[u])
continue;
fa[v] = u;
dfs(v);
if (len[v] > len[wson[u]])
wson[u] = v;
len[u] = max(len[u], len[v]);
}
++len[u];
}
int *f[N], *id, ans[N];
void dp(int u)
{
if (wson[u])
{
f[wson[u]] = f[u] + 1;
dp(wson[u]);
ans[u] = ans[wson[u]] + 1;
}
f[u][0] = 1;
for (int i = G.head[u]; i; i = G.nxt[i])
{
int v = G.to[i];
if (v == fa[u] || v == wson[u])
continue;
f[v] = id;
id += len[v];
dp(v);
for (int j = 0; j <= len[v] - 1; ++j)
{
f[u][j + 1] += f[v][j];
if (make_pair(f[u][j + 1], -(j + 1)) > make_pair(f[u][ans[u]], -ans[u]))
ans[u] = j + 1;
}
}
if (f[u][ans[u]] == 1)
ans[u] = 0;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v;
G.push(u, v);
G.push(v, u);
}
dfs(1);
id = new int[n + 1];
f[1] = id;
id += len[1];
dp(1);
for (int i = 1; i <= n; ++i)
{
cout << ans[i] << "\n";
}
return 0;
}
```
### [P3899 湖南集训 更为厉害](https://www.luogu.com.cn/problem/P3899)
#### 题意
给定一棵树。有 $q$ 次询问，每一次给定 $a$ 和 $x$，问有多少个树上二元组 $(b,c)$ 满足 $a$ 和 $b$ 均为 $c$ 的祖先，且 $a$ 和 $b$ 距离不超过 $x$。要求 $a\not=b\not=c$。
$1\le n,q\le 3\times 10^{5}$。
#### 解法
$b$ 是 $a$ 祖先的情况是 naïve 的，只考虑 $b$ 在 $a$ 的子树中的情况，那么每一个 $b$ 的贡献是 $sz_b-1$。也就是说现在要求 $a$ 子树中，除了 $a$ 以外，到 $a$ 距离不超过 $x$ 的所有点的子树大小减一之和。
每一个点视作一个（深度，DFN 序）的二元组，那么可以进行二维数点，用主席树或离线树状数组都可以维护。但是还可以选择使用线性复杂度的长链剖分优化 DP。
设 $f_{i,j}$ 表示 $i$ 子树，到 $i$ 距离不超过 $j$ 的答案之和。那么转移就是
$$
f_{i,j}=\sum_{k\in son(i),k\not=i}f_{k,j-1}+sz_k-1
$$
有一维与深度有关，可以使用长链剖分进行优化。套路地，轻儿子的答案可以暴力合并，重儿子的直接复制。
然而这里需要加一个常数，所以需要打标记。具体来说，每一个点维护一个值 $tag_i$ 表示其对于所有 $j$，$f_{i,j}$ 要加上的常数是多少。其需要继承所有儿子的 $tag$，再加上所有儿子的 $sz-1$。但是注意到 $f_{i,0}$ 显然等于 $0$，因为距离为 $0$ 的不能加上 $tag$ 的值，所以将 $f_{i,0}$ 减去 $tag_i$。
需要将所有询问离线，在求出 $f_i$ 之后立刻回答 $i$ 的所有询问，否则，在 $i$ 被合并到父亲时，其信息会被改变。
#### 代码
[Submission](https://www.luogu.com.cn/record/197601943)