10pts,悬关求条
查看原帖
10pts,悬关求条
775591
Yzc10729楼主2025/8/4 15:20
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
vector<int> G[N];
int d1,d2;
int d[N],g[N];
int len=0;
int c[N],f[N],vis[N];
void dfs(int x,int fa){
	int m1=-1,m2=-1;
	for(int i=0;i<G[x].size();++i)
	{
		int y=G[x][i];
		if(y==fa)continue;
		dfs(y,x);
		int tmp=d[y]+1;
		d[x]=max(d[x],tmp);
		if(tmp>m1){
            m2=m1,m1=tmp;
        }
		else if(tmp>m2)m2=tmp;
	}
	g[x]=max(max((int)0,m1+m2),max(m1,m2));
	len=max(len,g[x]);
}
void calc(int x){
    len=0;
    dfs(x,0);
    c[x]=len;
}
int find(int x){
    if(f[x]==x)return x;
    f[x]=find(f[x]);
    return f[x];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    int x,y;
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        f[find(x)]=find(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(f[i]==i)calc(i);
    }
    int opt;
    for(int i=1;i<=q;i++){
        cin>>opt;
        if(opt==1){
            cin>>x;
            cout<<c[find(x)]<<"\n";
        }else{
            cin>>x>>y;
            int dx=find(x),dy=find(y);
            if(dx==dy)continue;
            int tmp=((c[dx]+1)>>1)+((c[dy]+1)>>1)+1;
            tmp=max(tmp,max(c[dx],c[dy]));
            f[dx]=dy;
            c[dy]=tmp;
        }
    }
    return 0;
}

求助dalao

2025/8/4 15:20
加载中...