【Cf Edu #47 F】Dominant Indices(长链剖分)

时间:2022-12-29 23:58:32

【Cf Edu #47 F】Dominant Indices(长链剖分)

要求每个点子树中节点最多的层数,一个通常的思路是树上启发式合并,对于每一个点,保留它的重儿子的贡献,暴力扫轻儿子将他们的贡献合并到重儿子里来。

参考重链剖分,由于一个点向上最多只有$log$条轻边,故每个点最多被合并$log$次。但这不是这题想说的。

由于我们只保留以深度为下标的信息,重链剖分就会多算,以此引出长链剖分,权且作为一个模板来学习。

长链剖分时,每个点以最深的儿子作为长儿子,其余为短儿子。

每个点$O(1)$继承长儿子的信息,将短儿子的信息合并上来。每个点只有作为短儿子时才保留以它为链头的一条长链上的信息,空间复杂度为$O(链长)$。

显然,每次短儿子被合并之后就不会再被访问到了,因为它合并到了一条比它更长的链,而所有的长链都不相交,每条链都以$O(链长)$被合并掉,故总复杂度是$O(n)$的。

这道题只要维护深度为$i$的节点的数量,取最大值即可。

 

$\bigodot$技巧&套路:

  • 以深度为下标的信息,可以考虑长链剖分。
  • 通常信息的合并,DSU on tree就可以了。
【Cf Edu #47 F】Dominant Indices(长链剖分)【Cf Edu #47 F】Dominant Indices(长链剖分)
 1 #include <cstdio>
 2 #include <vector>
 3 
 4 const int N = 1000005;
 5 
 6 int n, hig[N], res[N], son[N], dep[N];
 7 std::vector<int> g[N];
 8 
 9 int yun, las[N], to[N << 1], pre[N << 1];
10 inline void Add(int a, int b) {
11     to[++yun] = b; pre[yun] = las[a]; las[a] = yun;
12 }
13 
14 void Dfs(int x, int Fa) {
15     for (int i = las[x]; i; i = pre[i]) if (to[i] != Fa) {
16         Dfs(to[i], x);
17         if (hig[x] < hig[to[i]] + 1) {
18             hig[x] = hig[to[i]] + 1;
19             son[x] = to[i];
20         }
21     }
22     if (!son[x]) {
23         g[x].push_back(1); return;
24     }
25     std::swap(g[x], g[son[x]]);
26     res[x] = res[son[x]];
27     for (int i = las[x]; i; i = pre[i]) if (to[i] != Fa) {
28         if (son[x] != to[i]) {
29             int nx = (int)g[x].size(), nt = (int)g[to[i]].size();
30             for (int j = 0; j < nt; ++j) {
31                 g[x][nx - nt + j] += g[to[i]][j];
32                 if (g[x][nx - nt + j] >= g[x][res[x]]) res[x] = nx - nt + j;
33             }
34         }
35     }
36     g[x].push_back(1);
37     if (g[x][res[x]] == 1) res[x] = (int)g[x].size() - 1;
38 }
39 
40 int main() {
41     scanf("%d", &n);
42     for (int i = 1, x, y; i < n; ++i) {
43         scanf("%d%d", &x, &y);
44         Add(x, y); Add(y, x);
45     }
46     Dfs(1, 0);
47     for (int i = 1; i <= n; ++i) {
48         printf("%d\n", hig[i] - res[i]);
49     }
50     
51     return 0;
52 }
View Code