只有30分 Help!
  • 板块P2195 HXY造公园
  • 楼主蒟酱厂妹
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/3/8 11:38
  • 上次更新2023/10/28 07:03:00
查看原帖
只有30分 Help!
310818
蒟酱厂妹楼主2022/3/8 11:38
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
std::vector<int>s[300007];
int f[300007],d[300007],d1[300007],d2[300007];
using std::cin;using std::cout;
int n,m,q,len;
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void dfs(int u,int fa){
	for(auto v:s[u]){
		if(v==fa)continue;else dfs(v,u);
		if(d1[v]+1>d1[u])d2[u]=d1[u],d1[u]=d1[v]+1;
		else if(d1[v]+1>d2[u])d2[u]=d1[v]+1;
	}
	d[u]=d1[u]+d2[u];
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int i,u,v,t,x,y,fx,fy;
	cin>>n>>m>>q;
	for(i=1;i<=n;i++)f[i]=i;
	for(i=1;i<=m;i++){
		cin>>u>>v,s[u].emplace_back(v),s[v].emplace_back(u);
		fx=find(u),fy=find(v);
		if(fx!=fy)f[fx]=fy;
	}
	for(i=1;i<=n;i++)if(find(i)==i)dfs(i,0);
	while(q--){
		cin>>t>>x;
		if(t==1){cout<<d[find(x)]<<'\n';continue;}else cin>>y,fx=find(x),fy=find(y);
		if(fx!=fy)d[f[fx]=fy]=std::max({d[fx],d[fy],((d[fx]+1)>>1)+((d[fy]+1)>>1)+1});
	}
	return 0;
}
2022/3/8 11:38
加载中...