题意
一棵树初始只有一个编号为 1 的根结点。
\(n\) 次操作，每次新增一个点作为 \(p_i\) 的子结点，询问更新后有多少点可以作为树直径的端点。
\(n\le3\times10^5\)。
题解
以下 \(dist(x,y)\) 表示点 \(x\) 与点 \(y\) 在树上的距离。
不难发现若干条直径必然叠合于至少一点，任选这些交点中的一点划开，维护该点左部可能成为直径端点的点集 \(L\) 与该点右部可能成为直径端点的点集 \(R\) 。
那么对于 \(L,R\) 需要满足从 \(L\) 中任取一点 \(L_0\) ， \(R\) 中任取一点 \(R_0\) ，\(dist(L0,R0)=直径长度\) 。
加点的时候动态维护 \(L,R\) 集合即可。
假设当前加入点 \(x\) ，我们从 \(L\) 中任取一点 \(L_0\) ， \(R\) 中任取一点 \(R_0\) ，计算 \(dist(x,L_0)=dis\_L,dist(x,R_0)=dis\_R\)。
若 \(max(dis\_L,dis\_R)<直径长度\) ，无事发生。
若 \(max(dis\_L,dis\_R)=直径长度\) ，那么若 \(dis\_L=直径长度\) ，将 \(x\) 加入 \(R\) ，另一种情况是类似的。
若 \(max(dis\_L,dis\_R)>直径长度\) ，那么用较大的更新直径长度，若使用 \(dis\_L\) 更新直径长度，那么将 \(x\) 加入点集 \(R\) ，
同时对于原点集 \(R\) 中的点，若其与 \(x\) 距离也为 \(dis\_L\) ，加入点集 \(L\) ，否则将这个点删去。
另一种情况是类似的。
每次询问的答案即为两个点集各自的大小之和。
点集 \(L,R\) 开两个 \(vector\) 维护即可。
不难发现每个点最多在 \(L,R\) 中各出现一次，不可能在任意一个点集中出现第二次，证明考虑反证法即可，因此时间复杂度是 \(O(n)\) 的。
代码
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
#define ReFor(i,r,l) for(int i=(r);i>=(l);--i)
const int N=300010;
using namespace std;
int n,len;
int dep[N],anc[N][20];
vector<int> L,R;
void add(int x,int fa_x)
{
dep[x]=(dep[fa_x]+1);
anc[x][0]=fa_x;
For(i,1,19)
anc[x][i]=anc[anc[x][i-1]][i-1];
return;
}
int LCA(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
ReFor(i,19,0)
{
if(dep[anc[x][i]]>=dep[y])
x=anc[x][i];
}
ReFor(i,19,0)
{
if(anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
}
if(x==y)
return x;
else
return anc[x][0];
}
int Distance(int x,int y){return (dep[x]+dep[y]-(2*dep[LCA(x,y)]));}
int main()
{
scanf("%d",&n);
{
len=0;
dep[0]=0;
add(1,0);
L.clear();
R.clear();
L.push_back(1);
};
For(_,1,n)
{
int i=(_+1),fa;
scanf("%d",&fa);
add(i,fa);
int distance_L=0,distance_R=0;
if(!L.empty())distance_L=Distance(i,L[0]);
if(!R.empty())distance_R=Distance(i,R[0]);
int maxx=max(distance_L,distance_R);
if(maxx==len){if(len==distance_L)R.push_back(i);else if(len==distance_R)L.push_back(i);}
if(maxx>len)
{
len=maxx;
if(len==distance_L)
{
for(auto id:R)
{
if(Distance(id,i)==len)
L.push_back(id);
}
R.clear();
R.push_back(i);
}
else if(len==distance_R)
{
for(auto id:L)
{
if(Distance(id,i)==len)
R.push_back(id);
}
L.clear();
L.push_back(i);
}
}
int ans=(L.size()+R.size());
printf("%d\n",ans);
}
return 0;
}