P2195 HXY造公园
题目描述
现在有一个现成的公园，有\(n\)个休息点和\(m\)条双向边连接两个休息点。众所周知，\(HXY\)是一个\(SXBK\)的强迫症患者，所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作：
1.对某个休息点\(x\)，查询公园中可以与这个点互相到达的休息点组成的路径中的最长路径。
2、对于两个休息点\(x\)、\(y\)，如果\(x\)，\(y\)已经可以互相到达则忽略此次操作。否则，在\(x\)可到达的所有休息点和\(y\)可到达的所有休息点（包括\(x\)，\(y\)自身）分别选择一个休息点，然后在这两个休息点之间连一条边，并且这个选择应该满足对于连接后的公园，\(x\)和\(y\)所在的区域（即\(x\)，\(y\)可达到的所有休息点和边组成的集合）中的最长路径的长度最小。
\(HXY\)打算进行\(q\)个操作，请你回答她的对于公园情况的询问（操作1）或者执行她的操作（操作2）。
注：所有边的长度皆为1。保证不存在环。最长路径定义为：对于点\(v_1,v_2......v_k\)，如果对于其中任意的\(v_i\)和\(v_i+1(1<=i<=k-1)\)，都有边相连接，那么\(v_j(1<=j<=k)\)所在区域的最长路径就是\(k-1\)。
输入输出格式
输入格式：
第一行，三个正整数，分别为\(n\)，\(m\)，\(q\)。
接下来的\(m\)行，每一行有两个正整数\(x_i\)，\(y_i\)，表示\(x_i\)和\(y_i\)有一条双向边相连。
再接下来的\(q\)行，每一行表示一个操作。
若该行第一个数为1，则表示操作1，之后还有一个正整数\(x_i\)，表示要查询的休息点。
若该行第一个数为2，则表示操作2，之后还有两个正整数\(x_i\)，\(y_i\)，表示需要执行操作的两个休息点。
输出格式：
输出行数为操作1的个数。
每行输出对于操作1询问的回答。
说明
对于10%的数据，只存在操作1。
对于30%的数据，\(1<=m<n<=20,1<=q<=5\)。
对于60%的数据，\(1<=m<n<=2000,1<=q<=1000\)。
对于100%的数据，\(1<=m<n<=3*10^5,1<=q<=3*10^5\)。
思路：
预处理每个连通块的直径，并查集维护属于哪个连通块
对于查询，直径查询点所在连通块直径
对于修改，通过模拟可以得到，两个直径长度分别为\(n\)和\(m\)的树合并的新树的直径是\(max(\lceil n/2 \rceil+\lceil m/2 \rceil+1,n,m)\)
Code:
#include <cstdio>
const int N=300010;
int max(int x,int y){return x>y?x:y;}
int n,m,q,f[N],head[N],to[N<<1],Next[N<<1],cnt,vis[N],len[N];
void add(int u,int v)
{
to[++cnt]=v;Next[cnt]=head[u];head[u]=cnt;
}
int l,r,mx;
void dfs1(int now,int fa,int dep)
{
vis[now]=1;
if(dep>mx)
mx=dep,r=now;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v!=fa)
dfs1(v,now,dep+1);
}
}
void dfs2(int now,int fa,int dep)
{
f[now]=r;
if(dep>mx)
mx=dep,l=now;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v!=fa)
dfs2(v,now,dep+1);
}
}
int Find(int x)
{
return f[x]=f[x]==x?x:Find(f[x]);
}
void Merge(int x,int y)
{
f[Find(y)]=Find(x);
}
void t_merge(int x,int y)
{
if(Find(x)==Find(y)) return;
len[Find(x)]=max((len[Find(y)]+1)/2+(len[Find(x)]+1)/2+1,max(len[Find(y)],len[Find(x)]));
Merge(x,y);
}
void get_d(int now)
{
mx=0;dfs1(now,now,1);
mx=0;dfs2(r,r,0);
len[r]=mx;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
int u,v,opt;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++)
if(!vis[i])
get_d(i);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&opt,&u);
if(opt==1) printf("%d\n",len[Find(u)]);
else {scanf("%d",&v);t_merge(u,v);}
}
return 0;
}
2018.7.12