玄5关求调
  • 板块学术版
  • 楼主Zhz105105
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/9/23 08:10
  • 上次更新2023/11/2 18:38:38
查看原帖
玄5关求调
1039294
Zhz105105楼主2023/9/23 08:10

CF455CCF455C

#include<bits/stdc++.h>
using namespace std;
//#define int  long long
#define kg putchar(' ')
#define endl puts("")
inline int read(){
    register int vis=1,ans=0;
    char x=getchar();
    while(x<'0'||x>'9'){
        if(x=='-')vis=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9'){
        ans=(ans<<1)+(ans<<3)+x-'0';
        x=getchar();
    }
    return vis*ans;
}
inline void print(register int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
const int N=6e5+90;
vector<int>e[N];
int dp[N];
int c[N];
int fa[N];
int len=0;
int n=read(),m=read(),q=read();
int root;
inline void tree_len(int x,int fa){
	int maxn1=-1e9,maxn2=-1e9;
	for(int i=0;i<e[x].size();i++){
		int y=e[x][i];
		if(y==fa)continue;
		tree_len(y,x);
		dp[x]=max(dp[x],dp[y]+1);
		if(dp[y]+1>maxn1)maxn2=maxn1,maxn1=dp[y]+1;
		else if(dp[y]+1>maxn2)maxn2=dp[y]+1;
	}
	len=max(len,max(maxn1+maxn2,max(maxn1,maxn2)));
}
inline void find_len(register int x){
	len=0;
	memset(dp,0,n+1);
	tree_len(x,0);
	c[x]=len;
}
inline int find(register int x){
	return (x==fa[x]?x:fa[x]=find(fa[x]));
//	if(x==fa[x])return x;
//	return fa[x]=find(fa[x]);
}
void hebing(int x,int y){
	x=find(x),y=find(y);
	if((x^y))fa[x]=y;
}
bool same(int x,int y){
	return !(find(x)^find(y));
}
void init(){
	for(register int i=1;i<=n;i++)fa[i]=i;
}
int opt,x,y,u,v;
signed main(){
	init();
	while(m--){
		u=read(),v=read();
		e[u].push_back(v),e[v].push_back(u);
		hebing(u,v);
	}
	for(register int i=1;i<=n;i++)if(fa[i]==i)find_len(i);
	while(q--){
		opt=read();
		if(opt&1){
			x=read();
			print(c[find(x)]),endl;
			continue;
		}else{
			x=find(read()),y=find(read());
			if(!(x^y))continue;
			hebing(x,y);
			c[find(x)]=max((((c[x]+1)>>1)+((c[y]+1)>>1))+1,max(c[x],c[y]));
		}
	}
    return 0;
}

#43 死活过不去

2023/9/23 08:10
加载中...