RE九个点求助
查看原帖
RE九个点求助
752094
MornHus楼主2023/5/30 21:29
// 1 <= m < n <= 300 000    1 <= q <= 300 000 
#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
int read(){
	int x=0;int f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();};
	return x*f;
}
int n,m,q;
int c[maxn];
int bcj[maxn];
int dp[maxn];
int g[maxn];
bool vis[maxn];
int l;
vector<int>tree[maxn];
int find(int x){
	if(bcj[x]==x)return x;
	return bcj[x]=find(bcj[x]);
}
void dfs(int now,int fa){
	int max1=-1;
	int max2=-1;
	for(int i=0,v;i<tree[now].size();i++,v=tree[now][i]){
		if(v==fa)continue;
		dfs(v,now);
		int temp=dp[v]+1;
		dp[now]=max(temp,dp[now]);
		if(temp>max1)max2=max1,max1=temp;
		else if(temp>max2)max2=temp;
	}
	g[now]=max(max(0,max1+max2),max(max1,max2));
	l=max(l,g[now]);
}
void calc(int x){
	l=0;
	dfs(x,0);
	c[x]=l;
}
int main(){
	
	n=read();
	m=read();
	q=read();
	for(int i=1;i<=n;i++){
		bcj[i]=i;
	}
	for(int i=1,x,y;i<=m;i++){
		x=read();
		y=read();
		bcj[find(x)]=find(y);
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(bcj[i]!=i|| vis[i])continue;
		calc(i);
		vis[i]=1;
	}
	while(q--){
		if(read()==1){
			cout<<c[find(read())]<<'\n';
		}else{
			int x=read(),y=read();
			x=find(x);
			y=find(y);
			if(x==y)continue;
			int temp=((c[x]+1)/2+(c[y]+1)/2)+1;
			temp=max(temp,max(c[y],c[x]));
			bcj[find(x)]=find(y);
			c[find(x)]=temp;
		}
	}
	return 0;
} 
2023/5/30 21:29
加载中...