caozy623's Blog

先把这几天要填的坑填完……T T

题意 by hongrock （语文水平及表达水平不高借鉴别人的题目翻译……）

题目就是N个点的无向图，先给出M条边，这M条边使得任意两点间要么不连通，要么仅有唯一的路径相连。

两个点如果连通就说明它们在同一个区域。

然后Q个询问

1 x，输出x所在区域的最长路径；

2 x y，如果x和y在同一区域则忽略，否则合并两个区域，并且合并之后的新区域的最长路径应该是最短的。

大概是这样……还要注意一点就是边的权值都为1.

然后比较容易想到用并查集来动态合并+维护区域信息。然后是要输出区域中的最长路径……合并的时候也要维护最

长路，使得其合并后是最短的，那么容易想到预处理出每个区域的直径……（其实就是类似树的直径），然后合并的

时候因为要求新的区域的最长路最短，那么我们定义一个点的最远距离是他到其他点的最远距离，我们合并直径是各

选一个最远距离最小的点，可以证明这个点一定是直径的中点。那么接下来就比较显然了，这个新的最长路一定是

max((path[y]+1)/2+(path[x]+1)/2+1,path[x],path[y])。还有求树的直径的话我这里就两次BFS即可，具体过程就是先选取一点u，跑出u的最远点yuan，然后从yuan跑出yuan的最远点y2，这时候y2和yuan之间的距离即为树的直径。证明这里就不证了，其实挺显然的……

~感谢skydec大爷的标程及其对题目思路的提示！

#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<algorithm>  
#include<vector>  
#include<string>  
#include<set>  
#include<queue>  
#include<stack>  
#include<map>  
#include<cmath>  
#include<cstdlib>  
#define ll long long  
#define maxn 600010  
#define inf 1000000000  
#define linf (1LL<<50)  
using namespace std;  
inline ll read()  
{  
    ll x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}  
    return x*f;  
}  
  
inline void read(char *s,int &ts)  
{  
    char x=getchar();  
    while(!(x>='a'&&x<='z'))x=getchar();  
    while(x>='a'&&x<='z')s[++ts]=x,x=getchar();  
}  
int n,m,que,tot=0;  
int q[maxn];  
struct data{  
    int to,next;  
}e[2*maxn];  
int head[maxn];  
int path[maxn];  
int d[maxn];  
int flag[maxn];  
int f[maxn];  
void line(int a,int b)  
{  
    tot++;  
    e[tot].to=b;  
    e[tot].next=head[a];  
    head[a]=tot;  
}  
int get(int x)  
{   
    return(x==f[x])?x:f[x]=get(f[x]);  
}  
int find(int x)  
{  
    d[x]=0;  
    flag[x]=x;  
    q[q[0]=1]=x;  
    int yuan=x;  
    for(int i=1;i<=q[0];i++)  
    {  
        int y=q[i];  
        for(int u=head[y];u;u=e[u].next)  
        if(flag[e[u].to]!=x)  
        {  
            flag[e[u].to]=x;  
            q[++q[0]]=e[u].to;  
            d[e[u].to]=d[y]+1;  
            if(d[e[u].to]>d[yuan])   
            yuan=e[u].to;  
        }  
    }  
    int y2=yuan;  
    d[yuan]=0;  
    q[q[0]=1]=yuan;  
    flag[yuan]=yuan;  
    for(int i=1;i<=q[0];i++)  
    {  
        int y=q[i];  
        for(int u=head[y];u;u=e[u].next)  
        if(flag[e[u].to]!=yuan)  
        {  
            flag[e[u].to]=yuan;  
            q[++q[0]]=e[u].to;  
            d[e[u].to]=d[y]+1;  
            if(d[e[u].to]>d[y2])  
            y2=e[u].to;  
        }  
    }  
    return d[y2];  
}  
  
int main()  
{  
    scanf("%d%d%d",&n,&m,&que);  
    for(int i=1;i<=n;i++)  
    f[i]=i;  
    for(int i=1;i<=m;i++)  
    {  
        int x,y;  
        scanf("%d%d",&x,&y);  
        line(x,y);  
        line(y,x);  
        if(get(x)!=get(y))  
        f[get(x)]=get(y);  
    }  
    for(int i=1;i<=n;i++)  
    if(i==get(i)) path[i]=find(i);  
    for(int i=1;i<=que;i++)  
    {  
        int pos;  
        scanf("%d",&pos);  
        if(pos==1)  
        {  
            int x;  
            scanf("%d",&x);  
            printf("%d\n",path[get(x)]);  
        }  
        else  
        {  
            int x,y;  
            scanf("%d%d",&x,&y);  
            x=get(x);y=get(y);  
            if(x==y) continue;  
            int u1=path[x];  
            int u2=path[y];  
            f[x]=y;  
            path[y]=(u1+1)/2+(u2+1)/2+1;  
            if(path[y]<u1) path[y]=u1;  
            if(path[y]<u2) path[y]=u2;  
        }  
    }  
    return 0;  
}