CF842E Nikita and game 题解

题意

一棵树初始只有一个编号为 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;
}