Codeforces Round #260 (Div. 1)??Civilization_html/css_WEB-ITnose

题目链接

题意：
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;}

登录后复制