[CF455C] Civilization

Description

给定 (n) 个点，(m) 条边组成的森林，有 (q) 次操作，每次操作要么询问某点所在连通块的直径，要么将两个不同的连通块连接，连接方式要使得连接后的直径最短。

Solution

设两个连通块的直径长度分别为 (l_1,l_2)，则连通后的直径长度为 (max(l_1,l_2,lceil l_1/2 ceil + lceil l_2/2 ceil + 1))

并查集维护即可

特别注意初态的直径是需要建图求解的

（据说一条链的 Test 121 可以卡常？）

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

int n,m,q,t1,t2,t3,t4;
int val[N],fa[N];

void init()
{
    for(int i=1;i<=n;i++) fa[i]=i;
}

int find(int p)
{
    return fa[p]==p ? p : fa[p]=find(fa[p]);
}

void merge(int p,int q)
{
    p=find(p); q=find(q);
    if(p!=q)
    {
        fa[p]=q;
        val[q]=max(max(val[p],val[q]),(val[p]+1)/2+(val[q]+1)/2+1);
    }
}

vector <int> g[N];
int vis[N],dis[N],maxpos,maxdis;

void dfs1(int p)
{
    vis[p]=1;
    if(dis[p]>maxdis)
    {
        maxdis=dis[p];
        maxpos=p;
    }
    for(int q:g[p])
    {
        if(vis[q]==0)
        {
            dis[q]=dis[p]+1;
            dfs1(q);
        }
    }
}

void dfs2(int p)
{
    vis[p]=2;
    if(dis[p]>maxdis)
    {
        maxdis=dis[p];
        maxpos=p;
    }
    for(int q:g[p])
    {
        if(vis[q]==1)
        {
            dis[q]=dis[p]+1;
            dfs2(q);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m>>q;

    init();
    for(int i=1;i<=m;i++)
    {
        cin>>t1>>t2;
        merge(t1,t2);
        g[t1].push_back(t2);
        g[t2].push_back(t1);
    }

    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            maxpos=0; maxdis=0;
            dfs1(i);
            int t=maxpos;
            maxpos=0; maxdis=0;
            dis[t]=0;
            dfs2(t);
            val[find(i)]=maxdis;
        }
    }

    for(int i=1;i<=q;i++)
    {
        cin>>t1;
        if(t1==1)
        {
            cin>>t2;
            cout<<val[find(t2)]<<endl;
        }
        else
        {
            cin>>t2>>t3;
            merge(t2,t3);
        }
    }
}