双倍经验：洛谷2195 HXY造公园
题意
给出一个有 $n(\le 3\times 10^5)$ 个点 $m(\le 3\times 10^5)$ 条边的森林。要求支持两种操作：
- 求 $x$ 所在树的直径
- 将 $x,y$ 所在的树合并，要求合并后树的直径最小
题解
合并可以用并查集来实现，用 $ans[x]$ 表示 $x$ 子树中的直径长度。
对于操作 $1$ ，直接输出 $ans[x]$ 。
对于操作 $2$ ，合并后的直径是以下两种情况的较大值：
- 还是原来某棵树的直径
- 有两棵树的直径组成
对于情况 $2$ ，将两棵树直径的中心连起来一定是最优的，这时的新直径长度为 $\lceil \frac{ans[x]}{2}\rceil + \lceil \frac{ans[y]}{2}\rceil+1$ 。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=300005;
struct Edge {
int next,to;
} edge[N<<1];
bool vis[N];
int cnt,head[N],n,m,q,a,b,c,fa[N],mx,mxi,ans[N];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline void init() { for (int i=1;i<=n;i++) fa[i]=i; }
int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); }
inline bool merge(int x,int y)
{
int gfx=getfa(x),gfy=getfa(y);
if (gfx==gfy) return 0;
return fa[gfx]=gfy,1;
}
void dfs(int x,int f,int dep)
{
vis[x]=1;
if (dep>mx) mx=dep,mxi=x;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
dfs(y,x,dep+1);
}
}
signed main()
{
n=read(); m=read(); q=read();
init();
for (int i=1;i<=m;i++)
{
a=read(); b=read();
add(a,b);
add(b,a);
merge(a,b);
}
for (int i=1;i<=n;i++)
{
if (vis[i]) continue;
mx=0; mxi=i;
dfs(i,0,0);
int rt=mxi; mx=0;
dfs(rt,0,0);
ans[getfa(i)]=mx; //得到 i 所在树的直径
}
while (q--)
{
a=read(); b=read();
if (a==1) printf("%d\n",ans[getfa(b)]);
else
{
c=read();
int x=getfa(b),y=getfa(c);
if (x==y) continue;
fa[x]=y; //合并
ans[y]=max((ans[x]+1)/2+(ans[y]+1)/2+1,max(ans[x],ans[y])); //新直径
}
}
return 0;
}