你是一个程序猿，现在有一棵新年树（并不是传统的带着叶子的树）——它有四个节点： $1$ ，$2$ ，$3$ ，$4$ . 其中$2$ ，$3$ ，$4$ 的父亲都是 $1$ .
新年里，程序猿们往往会做一些有趣的事情。你则选择以往这棵树上加节点来取乐。 一个添加节点的操作是这样的：
- 找到树上的一个叶子结点 $v$ .
- 设现在树上有 $n$ 个节点，那么你现在会加入两个节点$n+1$ 和 $n+2$ ，它们都会成为 $v$ 的儿子.
你的任务是在做 $q$ 次这样的操作，并在每做完一次后计算一次树的直径。来吧，我们一起来解决这道新年问题吧！
链接
Codeforces
伪题解
我们考虑树形dp计算树的直径的过程。
我们如果令 $f[i]$ 为以 $i$ 为根的子树中最长的链的长度，$g[i]$ 为以 $i$ 为根的子树中的直径长度（过根节点），那么就有如下转移：
$$
f[v] = \max(f[v_1] + f[v_2]) + 1\
g[v] = f[v_1] + f[v_2] + 2
$$
如果我们令 $dep[v]$ 为 $v$ 的深度，那么我们可以将第一个改写如下：
$$
f[v] = \max _ {v_i \text{ is in the subtree of } v}(dep[v_i]) - dep[v]
$$
我们可以用倍增在 $O(\log n)$ 的时间内找到第一个不需要更新的位置，然后在倍增上用 $O(\log n)$ 的时间内更新 $f$ 值，计算得到 $delta$（每次深度只增加1，所以一定会只有一个delta），然后将 $g$ 修改维护即可。
看了 Tutorial 之后有些自闭，题解给出了一个非常轻松愉悦的办法。
题解
我们思考 $\text{dfs}$ 计算直径的过程，从一个节点找到最远的一个节点，这个节点一定是直径的一个端点，然后我们再进行一遍 $\text{dfs}$ 最远点就是直径的另一个的端点。
所以我们考虑从根节点进行第一次 $\text{dfs}$ ，找到最远的第一个节点（事实上是深度最大的节点之一皆可）。
如果我们给一个节点新建了两个子节点，我们发现它们的父亲是当前最远的节点，那么答案一定增加且只增加了 $1$ ；
否则，答案只有可能被当前最远的节点和新增加的节点之间的距离更新。
那么就可以倍增维护 $\text{LCA}$ 计算树上距离，在 $O(n \log n)$ 的时间内解决这个问题。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1001000,logn = 22;
int q;
int f[MAXN][logn],dep[MAXN],t[MAXN];
int lca(int x,int y){
if(dep[x] < dep[y]) swap(x,y);
for(int i = logn-1;i>=0;--i){
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = logn-1;i>=0;--i){
if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
}
return f[x][0];
}
void addnode(int x,int fa){
f[x][0] = fa,dep[x] = dep[fa]+1;
for(int i = 1;i<logn;i++){
f[x][i] = f[f[x][i-1]][i-1];
}
}
int caldis(int x,int y){
return dep[x] + dep[y] - 2 * dep[lca(x,y)];
}
void init(){
scanf("%d",&q);
for(int i = 1;i<=q;i++)
scanf("%d",&t[i]);
}
void solve(){
dep[1] = 1,dep[2] = dep[3] = dep[4] = 2;
f[2][0] = f[3][0] = f[4][0] = 1;
int maxdep = 2,maxnode = 2,ans = 2,n = 4;
for(int i = 1;i<=q;i++){
int x = t[i];
addnode(++n,x),addnode(++n,x);
if(dep[x] == maxdep){
maxdep++,maxnode = n,ans++;
}
else{
ans = max(ans,caldis(maxnode,n));
}
printf("%d\n",ans);
}
}
int main(){
init();
solve();
return 0;
}
|
