52pts,求调
查看原帖
52pts,求调
1200401
wnqnld_llx楼主2025/4/2 16:04
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+1;
int tr[maxn][maxn/1000],cnt[maxn],maxlen1=-INT_MAX,num1,maxlen2=-INT_MAX,num2,vis[maxn],vis2[maxn];
void dfs(int u,int len){
	if(maxlen1<=len){
		maxlen1=len;
		num1=u;
	}
	for(int i=1;i<=cnt[u];i++){
		int son=tr[u][i];
		if(!vis[son]){
			vis[u]=1;
			dfs(son,++len);
			vis[son]=0;
			len--;
		}
	}
}
void dfs2(int u,int len){
	//cout<<u<<" "<<len<<"\n";
	if(maxlen2<=len){
		maxlen2=len;
	}
	for(int i=1;i<=cnt[u];i++){
		int son=tr[u][i];
		if(!vis2[son]){
			vis2[u]=1;
			dfs2(son,++len);
			vis2[son]=0;
			len--;
		}
	}
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		tr[a][++cnt[a]]=b;
		tr[b][++cnt[b]]=a;
	}
	vis[1]=1;
	dfs(1,0);
	vis[num1]=1;
	dfs2(num1,0);
	cout<<maxlen2;
	return 0; 
}
2025/4/2 16:04
加载中...