题目链接

• 题意：

  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;
}