题意

P2195 codeforces 455c，两道一样的题

给出一个由 $n$ 个点，$m$ 条边组成的森林，有 $q$ 组询问,每次询问有以下两种情况

输入 $op=1$ 时：给出点 $x$，输出点 $x$ 所在的树的直径。
输入 $op=2$ 时：给出点 $x,y$，（如果 $x,y$ 在同一棵树中则忽略此操作）选择任意两点 $u,v$，使得 $u 跟 $x$ 在同一棵树中且 $v$ 跟 $y$ 在同一棵树中。将 $u,v$ 之间连一条边，使得连边后的到的新树的直径最小。

思路

首先毫无疑问找到每一棵树的“核”，即直径的终点。在此基础上我们保存 $deepes{t}_i$ 和 $deepest{2}_i$，表示以这个核为根节点的树前两个最长的链（互不重合），则 $deepes{t}_i+deepest{2}_i$ 则表示当前直径。

考虑操作 $1$，我们输出 $deepes{t}_i+deepest{2}_i$ 即可。

考虑操作 $2$。因为合并两棵树（如果已经是一棵树则不用合并，合并和找根节点用并查集可以实现，可前往并查集入门学习）后树的直径长度不会改变，因此令 $x\leftarrow find(x),y\leftarrow find(y)$，$find$ 操作表示并查集中找到根节点。合并时显而易见只要合并两个根节点即可

• 考虑 $deepes{t}_x=deepes{t}_y$ 情况，如图所示，原来 $4,5,6$ 和 $1,2,3$ 分别为 $2$ 棵树，加根后因为 $1$ 加到 $4$ 地下，$deepes{t}_x\leftarrow deepes{t}_x+1$。

• 考虑 两个最深的链不等的情况，不妨令 $deepes{t}_x>deepes{t}_y$，则考虑对第二深的链的影响。如果 $deepes{t}_y+1>deepest{2}_x$，则更新 $deepest{2}_x=deepes{t}_y+1$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fat[600005];
int find(int x) {return fat[x] == x?x:fat[x] = find(fat[x]);
}
int head[600005],nex[1200005],to[1200005],cnt;
int add(int x,int y) {nex[++cnt] = head[x];head[x] = cnt;to[cnt] = y;
}
int n,m,q; 
bool v[600005];
int maxx,ed1,ed2,root;
int deepest[600005],deepest2[600005];
void find_edge1(int now,int fa,int deep) {for(int i = head[now];i;i = nex[i]) {if(to[i] != fa) find_edge1(to[i],now,deep + 1);}if(deep >= maxx) {maxx = deep;ed1 = now;}return;
}
void find_edge2(int now,int fa,int deep) {for(int i = head[now];i;i = nex[i]) {if(to[i] != fa) find_edge2(to[i],now,deep + 1);}if(deep >= maxx) {maxx = deep;ed2 = now;}return;
}
void find_root(int now,int fa,int deep) {if(now == ed2) {v[now] = 1;}for(int i = head[now];i;i = nex[i]) {if(to[i] != fa) {find_root(to[i],now,deep + 1);if(v[to[i]]) v[now] = 1;}}if(v[now] and deep == maxx / 2) {root = now;deepest[root] = maxx - deep;deepest2[root] = maxx / 2;}
}
void biaoji(int now,int fa) {for(int i = head[now];i;i = nex[i]) {if(to[i] != fa) biaoji(to[i],now);}v[now] = 1;fat[now] = root;
}
signed main() {scanf("%lld %lld %lld",&n,&m,&q);for(int i = 1;i <= n;i++) fat[i] = i;while(m--) {int x,y;scanf("%lld %lld",&x,&y);add(x,y),add(y,x);}for(int i = 1;i <= n;i++) {if(!v[i]) {maxx = 0;find_edge1(i,i,0);maxx = 0;find_edge2(ed1,ed1,0);find_root(ed1,ed1,0);biaoji(ed1,ed1);//	printf("%lld %lld %lld\n",ed1,ed2,root);}}for(int i = 1;i <= q;i++) {int op,x,y;scanf("%lld",&op);if(op == 1) {scanf("%lld",&x);printf("%lld\n",deepest[find(x)] + deepest2[find(x)]);}if(op == 2) {scanf("%lld %lld",&x,&y);x = find(x),y = find(y);if(x == y) continue;//printf("%lld %lld\n",deepest[x],deepest[y]);if(deepest[x] == deepest[y]) {fat[y] = x;deepest[x]++;deepest2[x] = deepest[y];}else if(deepest[x] > deepest[y]) {fat[y] = x;if(deepest2[x] < deepest[y] + 1) deepest2[x] = deepest[y] + 1;}else {fat[x] = y;if(deepest2[y] < deepest[x] + 1) deepest2[y] = deepest[x] + 1;}}}return 0;
}