题目链接
n个点，m条边的森林，q次操作。每次操作：1、询问x所在树的直径 2、合并x和y所在的树，使得合并后的直径最小
(1?≤?n?≤?3·105; 0?≤?m?<?n ; 1?≤?q?≤?3·105)
没有读到图是森林。。。做的好纠结
最开始将每个树都求一下直径，之后使用并查集处理，每次合并直径：至少是两个树的直径，或者将两个直径的最中间的部分连接求直径
const int MAXN = 310000;int rt[MAXN], ans[MAXN];VI G[MAXN];bool vis[MAXN];void init(int n){ REP(i, n) { vis[i] = false; ans[i] = 0; G[i].clear(); rt[i] = i; }}int find(int n){ return n == rt[n] ? n : rt[n] = find(rt[n]);}void merge(int a, int b){ int fa = find(a), fb = find(b); if (fa != fb) { rt[fa] = fb; ans[fb] = max(ans[fb], (ans[fb] + 1) / 2 + (ans[fa] + 1) / 2 + 1); ans[fb] = max(ans[fa], ans[fb]); }}int Max, id;void dfs(int u, int fa, int dep){ vis[u] = true; REP(i, G[u].size()) { int v = G[u][i]; if (v != fa) dfs(v, u, dep + 1); } if (dep > Max) { Max = dep; id = u; }}int main(){ int n, m, q; while (~RIII(n, m, q)) { init(n + 1); REP(i, m) { int a, b; RII(a, b); G[a].push_back(b); G[b].push_back(a); int fa = find(a), fb = find(b); rt[fa] = fb; } FE(i, 1, n) { if (!vis[i]) { Max = -1; dfs(i, -1, 0); Max = -1; dfs(id, -1, 0); ans[find(i)] = Max; } } REP(i, q) { int op; RI(op); if (op == 2) { int a, b; RII(a, b); merge(a, b); } else { int a; RI(a); WI(ans[find(a)]); } } } return 0;}