Codeforces Round #260 (Div. 1), problem: (C) Civilization

題目給你一堆樹，和一堆操作：
(1) 問一棵樹的直徑
(2) 把兩個樹合併，合併方法要使合併後的直徑最小

總之把兩棵樹合併後得到的最小直徑，只跟原本直徑有關。
最後再加上disjoint set 維護即可。

最後還是看了一下錯在哪比測資，才知道我忘了判兩個city在同一個region

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
typedef pair<int,int> pii;
int fat[300001];
int rk[300001];
int getfat(int x){
    if(fat[x] == x) return x;
    fat[x] = getfat(fat[x]);
    return fat[x];
}
int onion(int x, int y){
    int fx = getfat(x), fy = getfat(y);
    if(rk[fx] > rk[fy]){
        fat[fy] = fx;
        return fx;
    }else{
        fat[fx] = fy;
        if(rk[fx] == rk[fy])
            rk[fy]++;
        return fy;
    }
}
int len[300001];
bool vis[300001] = {0};
vector<int> to[300001];
pii dfs(int prc, int gid){
    vis[prc] = true;
    fat[prc] = gid;
    int getR=0;
    vector<int> getH(2, 0);
    for(int lx = 0;lx < to[prc].size();lx++){
        if(vis[to[prc][lx]]) continue;
        pii gg = dfs(to[prc][lx], gid);
        getR = max(getR, gg.first);
        getH.push_back(gg.second+1);
    }
    int sz = getH.size();
    sort(getH.begin(), getH.end());
    getR = max(getR, getH[sz-1]+getH[sz-2]);
    return pii(getR, getH[sz-1]);
}
int main()
{
    int n, m, q; scanf("%d %d %d", &n, &m, &q);
    for(int lx = 0;lx < m;lx++){
        int a, b;scanf("%d %d", &a, &b); a--, b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    for(int lx = 0;lx < n;lx++){
        if(vis[lx]) continue;
        pii get = dfs(lx, lx);
        len[lx] = get.first;
        rk[lx] = 2;
    }
    int o, a, b;
    while(q--){
        scanf("%d", &o);
        if(o == 1){
            scanf("%d", &a); a--;
            printf("%d\n", len[getfat(a)]);
        }else{
            scanf("%d %d", &a, &b);
            a--, b--;
            int ca = getfat(a), cb = getfat(b);
            if(ca == cb) continue;
            int la = len[ca], lb = len[cb];
            int nc = onion(ca, cb);
            if(la == lb)
                len[nc] = (la+1)/2 + (lb+1)/2 + 1;
            else{
                if(la < lb) swap(la, lb);

                len[nc] = (la+1)/2+max(1+(lb+1)/2, la/2);
            }
            //printf("set %d -> %d\n", nc, len[nc]);
        }
    }
    return 0;
}