[CF 455C] Civilization

作法：

由條件知到他的圖會是一個森林。這題只要注意到連接兩個連通塊時連接兩連通塊的重心是最好的選擇，因此只要對每個連通塊計算他的最長鍊是多長就可以了，最長鍊的計算方法為：先任遠一個點對他DFS，找出離他最遠的點，再以找到的那個點當根做一次DFS，所得到的最長距離就是這棵樹的最長練了。假設兩個連通分量的最長鍊分別為$x,y$，那麼連接他們的重心之後會產生一條長為$\left \lceil \frac{x}{2} \right \rceil+\left \lceil \frac{y}{2} \right \rceil+1$的鍊，再和$x,y$取 max 就是新連通塊的最長鍊長度了，至於實作用個 disjoint set 並維護好最長鍊值就可了。類似的題目還有 IOI 2013 Dreaming （HOJ 288）。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=600000+10 ;
 
int fa[maxn],fcnt ;
int getfa(int x)
{
    return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
int val[maxn] ;
void join(int x,int y)
{
    x=getfa(x) ; y=getfa(y) ;
    if(x==y) return ;
    val[++fcnt]=max(max(val[x],val[y]),1+(val[x]+1)/2+(val[y]+1)/2) ;
    fa[fcnt]=fcnt ;
    fa[x]=fa[y]=fcnt ;
}
 
vector<int> v[maxn] ;
int d[maxn] ;
void dfs(int x,int f,int dep,int &id,int &M)
{
    d[x]=dep ;
    if(dep>M) M=dep , id=x ;
    for(auto i : v[x]) if(i!=f)
        dfs(i,x,dep+1,id,M) ;
}
 
int getlen(int x)
{
    int id,M=-1 ;
    dfs(x,-1,0,id,M) ;
    M=-1 ;
    dfs(id,-1,0,id,M) ;
    return M ;
}
 
main()
{
    int n,m,Q ; scanf("%d%d%d",&n,&m,&Q) ;
    for(int i=1;i<=n;i++) fa[i]=i , fcnt++ ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ; v[y].push_back(x) ;
        fa[getfa(x)]=getfa(y) ;
    }
    for(int i=1;i<=n;i++) if(fa[i]==i)
        val[i]=getlen(i) ;
    while(Q--)
    {
        int t,x,y ; scanf("%d",&t) ;
        if(t==1) scanf("%d",&x) , printf("%d\n",val[getfa(x)]) ;
        else scanf("%d%d",&x,&y) , join(x,y) ;
    }
}