C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+10;
int h[N],e[2*N],ne[2*N],idx;
int up[N];
int d1[N],d2[N],path[N];
int n,maxd;
bool has_father[N],st[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs_d(int u,int father){
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father) continue;
dfs_d(j,u);
int d=d1[j]+1;
if(d>d1[u]) {
d2[u]=d1[u],d1[u]=d;
path[u]=j;
}
else if(d>d2[u]) d2[u]=d;
}
maxd=max(maxd,d1[u]+d2[u]);
}
void dfs_u(int u,int father){
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father) continue;
up[j]=up[u]+1;
if(path[u]==j)
up[j]=max(up[j],d2[u]+1);
else up[j]=max(up[j],d1[u]+1);
dfs_u(j,u);
}
}
int main(){
cin>>n;
memset(h,-1,sizeof h);
for(int j=0;j<n;j++){
int i,k; cin>>i>>k;
add(i,k);
add(k,i);
}
dfs_d(0,-1);
dfs_u(0,-1);
for(int i=0;i<n;i++){
int d[3]={d1[i],d2[i],up[i]};
sort(d,d+3);
if(d[1]+d[2]==maxd) {
st[i]=true;
cout<<i<<endl;
}
}
return 0;
}