题目传送门

前置知识

树的直径 | 最近公共祖先 | 并查集

解法

一个显而易见的结论：设点集 $A$ 的直径的两个端点为 $u_{1},v_{1}$，另一个点集 $B$ 的直径的两个端点为 $u_{2},v_{2}$，则 $A \bigcup B$ 的直径端点一定是 $\{ u_{1},v_{1},u_{2},v_{2} \}$ 中的两个。

还有另外一个结论：点集 $A$ 中一个点 $x$ 到点集中其他点中最远点的距离一定是到直径两个端点的距离取 $\max$。

• 证明
  • 当 $x$ 在直径上时，显然。
  • 当 $x$ 不在直径上时，先走到直径上，就转化到了上述情况。

并查集维护连通块内直径的两个端点即可。

倍增来支持动态连边操作，做法同 luogu P3302 [SDOI2013] 森林。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
	ll nxt,to;
}e[200010];
ll head[200010],fa[200010][25],dep[200010],N,cnt=0;
void add(ll u,ll v)
{
	cnt++;
	e[cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
void dfs(ll x,ll father)
{
	dep[x]=dep[father]+1;
	fa[x][0]=father;
	for(ll i=1;i<=N;i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(ll i=head[x];i!=0;i=e[i].nxt)
	{
		if(e[i].to!=father)
		{
			dfs(e[i].to,x);
		}
	}
}
ll lca(ll x,ll y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	for(ll i=N;i>=0;i--)
	{
		if(dep[x]+(1<<i)<=dep[y])
		{
			y=fa[y][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	else
	{
		for(ll i=N;i>=0;i--)
		{
			if(fa[x][i]!=fa[y][i])
			{
				x=fa[x][i];
				y=fa[y][i];
			}
		}
		return fa[x][0];
	}
}
ll dis(ll x,ll y)
{
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
struct DSU
{
	ll fa[200010],pt[200010][2],tmp[5];
	void init(ll n)
	{
		for(ll i=1;i<=n;i++)
		{
			fa[i]=i;
			pt[i][0]=pt[i][1]=i;
		}
	}
	ll find(ll x)
	{
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	void merge(int x,int y)
	{
		dfs(y,x);
		x=find(x);
		y=find(y);
		fa[y]=x;
		ll maxx=0;
		tmp[1]=pt[x][0];
		tmp[2]=pt[x][1];
		tmp[3]=pt[y][0];
		tmp[4]=pt[y][1];
		for(ll i=1;i<=4;i++)
		{
			for(ll j=i+1;j<=4;j++)
			{
				if(dis(tmp[i],tmp[j])>maxx)
				{
					maxx=dis(tmp[i],tmp[j]);
					pt[x][0]=tmp[i];
					pt[x][1]=tmp[j];
				}
			}
		}
	}
	ll ask(ll x)
	{
		ll y=find(x);
		return max(dis(x,pt[y][0]),dis(x,pt[y][1]));
	}
}D;
int main()
{
	ll q,x,n=0,i;
	char pd;
	cin>>q;
	N=log2(q)+1;
	D.init(q);
	for(i=1;i<=q;i++)
	{
		cin>>pd>>x;
		if(pd=='B')
		{
			n++;
			if(x==-1)
			{
				dfs(n,0);
			}
			else
			{
				D.merge(x,n);
			}
		}
		else
		{
			cout<<D.ask(x)<<endl;
		}
	}
	return 0;
}

D59 树的直径 树上前缀和 P4271 [USACO18FEB] New Barns P

// 树的直径 树上前缀和 O(nlogn)
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int h[N],idx,to[N],ne[N];
void add(int u,int v){
  to[++idx]=v;ne[idx]=h[u];h[u]=idx;
}
int n,m,opt[N],q[N],point[N][2];

int dep[N],fa[N][21],root[N];
void dfs(int u){
  for(int i=h[u]; i; i=ne[i]){
    int v=to[i];
    dep[v]=dep[u]+1; fa[v][0]=u;
    for(int i=1;i<=20;++i) fa[v][i]=fa[fa[v][i-1]][i-1];
    root[v]=u==0?v:root[u]; //记录v所在树的树根
    dfs(v);
  }
}
int lca(int u,int v){
  if(dep[u]<dep[v]) swap(u,v);
  for(int i=20;i>=0;--i)if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
  if(u==v) return u;
  for(int i=20;i>=0;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
  return fa[u][0];
}
int dis(int u,int v){
  return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int main(){
  scanf("%d",&m);
  for(int i=1,x; i<=m; ++i){
    char ch[2]; scanf("%s %d",ch,&x);
    opt[i]=(ch[0]=='B'?1:2);
    if(opt[i]==1) add(x==-1?0:x, q[i]=++n); //0是超级源点
    else q[i]=x;
  }
  dfs(0); //倍增预处理 dep,fa,root 数组
  for(int i=1; i<=n; ++i) point[i][0]=point[i][1]=i; //直径的两个端点初值重合
  
  for(int i=1,x,d,d0,d1; i<=m; ++i){
    if(opt[i]==1 && q[i]!=-1){
      x=root[q[i]]; //取出新增点qi所在树的树根x，把新直径的两个端点记录在树根x上
      d=dis(point[x][0],point[x][1]); //求出当前树x的旧直径
      d0=dis(q[i],point[x][0]);       //求出qi到x的直径左端的距离
      d1=dis(q[i],point[x][1]);       //求出qi到x的直径右端的距离
      if(d==0) point[x][0]=q[i];      //如果旧直径为0，就让新直径左端点为qi
      else if(d0>d) point[x][1]=q[i]; //如果qi到左端点的距离更大，就让新直径右端点为qi
      else if(d1>d) point[x][0]=q[i]; //如果qi到右端点的距离更大，就让新直径左端点为qi
    }
    if(opt[i]==2){
      x=root[q[i]]; //取出点qi所在树的树根x，计算点qi到当前树x的直径端点的最远距离
      printf("%d\n",max(dis(q[i],point[x][0]),dis(q[i],point[x][1])));
    }
  }
}