前置知识
解法
一个显而易见的结论：设点集 \(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;
}