456E - Civilization - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define intt long long
#define pb push_back
#define pf push_front
#define pi pair<int,int>
#define pll pair<ll,ll>
#define in insert
#define AK ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define e endl
#define sc second
#define fr first
#define ll long long
#define Vi vector<int>
#define Vpi vector<pair<int,int> >
#define Vll vector<ll>
#define Vpll vector<pll>
#define Vs vector<string>
#define all(a)  a.begin(),a.end()
#define Sort(a) sort(all(a))
#define Rev(a)  reverse(all(a))
#define yes cout<<"YES"<<e
#define no  cout<<"NO"<<e
#define VVi vector<Vi>
#define VVll vector<Vll>
#define deb(x) cout<< #x << " = " << x << e;
#define stldeb(x) {cout<< #x << " = " ;for(auto it : x)cout<< it << " ";cout<< e;}
#define stldeb2(x) {cout<< #x << " = ";for(auto it : x)cout<< "{ "<< it.fr << " , " << it.sc << " } " << e;}
#define mymemset(x,val,i,n) {for(int j=i;j<=n;j++)x[j]=val;}
#define sz(x) x.size()
#define Mid (st+en)/2
#define log2(x) (31^__builtin_clz(x))
#define ever (;;)
const int N= 3e5+10;
int pa[N],Rank[N],Size[N],Diameter[N],vis[N];
void make_set(int v)
{
    pa[v]=v;
    Rank[v]=0;
    Size[v]=1;
    return;
}
int root(int i)
{
    if(pa[i]==i)
        return i;
    return pa[i]= root(pa[i]);
}
bool Union(int a, int b)
{
    a= root(a);
    b= root(b);
    if(a!=b)
    {
        if(Rank[a]<Rank[b])
            swap(a,b);
        pa[b]=a;
        if(Rank[a]==Rank[b])
            Rank[a]++;
        Size[a]+=Size[b];
    }
    return a!=b;
}

Vi adj[N];
ll ans;
ll DFS(int node,int par)
{
    ll mx1=0,mx2=0;
    vis[node]=1;
    for(auto Child : adj[node])
    {
        if(Child==par)
            continue;
        ll res = DFS(Child,node)+ 1;
        if(res>=mx2)
            mx1=mx2,mx2=res;
        else if(res>mx1)
            mx1=res;
    }

    ans=max(ans,mx1+mx2);
    return mx2;
}
int main()
{
    AK;
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q) ;
    for(int i=1;i<=n;i++)
        make_set(i);
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        Union(u,v);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            ans=0;
            DFS(i,-1);
            Diameter[root(i)]=ans;
        }
    while(q--)
    {
        int t,u,v;
        scanf("%d%d",&t,&u);
        if(t==1)
        {
            int rt = root(u);
            printf("%d \n",Diameter[rt]);
            continue;
        }
        scanf("%d",&v);
        int tempu=u,tempv=v;
        u=root(u);
        v=root(v);
        if(u!=v)
        {
            /*deb(Diameter[u]);
            deb(Diameter[v]);*/
            int mx= max(Diameter[u],Diameter[v]);
            int res= max(mx,(Diameter[u]/2+ Diameter[u]%2)+(Diameter[v]/2+Diameter[v]%2)+1);
            Diameter[u]= res;
            Diameter[v]= res;
            /*deb(Diameter[u]);
            deb(Diameter[v]);*/
            Union(tempu,tempv);
        }
    }
    return 0;
}