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

Question link

Question meaning:
A forest of n points, m edges, q operations. Each operation: 1. Query the diameter of the tree where x is located 2. Merge the trees where x and y are located so that the merged diameter is the smallest
(1?≤?n?≤?3·105; 0?≤?m?

Analysis:
Didn’t read that the picture is a forest. . . Well done
First find the diameter of each tree, and then use union-find processing to merge the diameters each time: at least the diameter of two trees, or connect the middle parts of the two diameters to find Diameter

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