这是一道双倍经验题 Luogu P2195
虽然Luogu P2195的题意很迷，但确实是双倍经验
先预处理出每棵树的直径，并用并查集维护哪些点在同一棵树里
对于\(1\)操作，直接输出就可以了
对于\(2\)操作，显然在两棵树直径的中点处连边最优。再用并查集维护一下即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
struct zzz {
int t, nex;
}e[300010 << 1]; int head[300010], tot;
void add(int x, int y) {
e[++tot].t = y;
e[tot].nex = head[x];
head[x] = tot;
}
int fa[300010];
int findd(int x) {
return fa[x] == x ? x : fa[x] = findd(fa[x]);
}
int que[300010], dis[300010], h, t;
int dia[300010];
void solve(int s) {
h = 1, t = 0; que[++t] = s; dis[s] = 1;
int maxn = -1, pos;
while(h <= t) {
int x = que[h++];
if(dis[x] > maxn) maxn = dis[x], pos = x;
for(int i = head[x]; i; i = e[i].nex) {
if(!dis[e[i].t])
que[++t] = e[i].t, dis[e[i].t] = dis[x] + 1;
}
}
for(int i = 1; i <= t; ++i) dis[que[i]] = 0;
h = 1, t = 0, que[++t] = pos; dis[pos] = 1;
maxn = -1;
while(h <= t) {
int x = que[h++];
if(dis[x] > maxn) maxn = dis[x];
for(int i = head[x]; i; i = e[i].nex) {
if(!dis[e[i].t])
que[++t] = e[i].t, dis[e[i].t] = dis[x] + 1;
}
}
int fx = findd(s);
dia[fx] = maxn-1;
}
int main() {
int n = read(), m = read(), q = read();
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
int fx = findd(x), fy = findd(y);
if(fx != fy) fa[fx] = fy;
add(x, y); add(y, x);
}
for(int i = 1; i <= n; ++i)
if(!dis[i]) solve(i);
for(int i = 1; i <= q; ++i) {
int opt = read(), x = read();
if(opt == 1) {
int fx = findd(x);
printf("%d\n", dia[fx]);
}
else {
int y = read();
int fx = findd(x), fy = findd(y);
if(fx != fy) {
fa[fx] = fy;
dia[fy] = max((dia[fx]+1 >> 1) + (dia[fy]+1 >> 1) + 1, max(dia[fx], dia[fy]));
}
}
}
return 0;
}