蒟蒻求救
  • 板块P2195 HXY造公园
  • 楼主_UUQ_
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/8/16 08:29
  • 上次更新2023/11/6 20:09:32
查看原帖
蒟蒻求救
84455
_UUQ_楼主2020/8/16 08:29

一直10分wa后面9个点,然后对着题解越改越像但还是A不了啊

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int maxn=3e6+10;
struct edge{
	int t,nex;
}e[maxn*2];
int fir[maxn],cnt;
int zhi[maxn];
void c(int f,int t){
	e[++cnt].t=t;
	e[cnt].nex=fir[f];
	fir[f]=cnt;
}
int fa[maxn];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void uni(int x,int y){
	if(find(x)!=find(y)){
		fa[find(x)]=find(y);
	}
}
int longest,longnum,tmp;
void dfs(int now,int fa,int d){
	if(d>longnum){
		longest=now;
		longnum=d;
	}
	for(int i=fir[now];i;i=e[i].nex){
		if(e[i].t==fa)continue;
		dfs(e[i].t,now,d+1);
	}
}
bool vis[maxn];
void weihu(int x,int y){
	if(find(x)==find(y))return;
	zhi[find(y)]=max(max(zhi[find(x)],zhi[find(y)]),(zhi[find(x)]+1)/2+(zhi[find(y)]+1)/2+1);
	fa[find(x)]=find(y);
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		c(x,y);
		c(y,x); 
		uni(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!vis[find(i)]){
			vis[find(i)]=1;
			longnum=-1;
			dfs(i,i,0);
			longnum=-1;
			tmp=longest;
			dfs(tmp,tmp,0);
			zhi[find(i)]=longnum;	
		}
	}
	while(q--){
		int f;
		scanf("%d",&f);
		if(f==1){
			int x;
			scanf("%d",&x);
			printf("%d\n",zhi[find(x)]);
		}else{
			int x,y;
			scanf("%d%d",&x,&y); 
			weihu(x,y);
		}
	}
	return 0;
}

2020/8/16 08:29
加载中...