很显然的换根dp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int son[100001];
int dis[100001];
int n;
int a,b;
int head[100001];
int p;
int dp[100001];
struct e{
int to;
int ne;
}ed[6000006];
void add(int f,int t){
p++;
ed[p].ne=head[f];
ed[p].to=t;
head[f]=p;
}
void dfs(int no,int f){
for(int i=head[no];i;i=ed[i].ne){
if(ed[i].to==f) continue;
dfs(ed[i].to,no);
son[no]+=son[ed[i].to];
dis[no]+=dis[ed[i].to]+son[ed[i].to];
}
son[no]++;
return ;
}
int ans,id;
void dfss(int no,int f){
for(int i=head[no];i;i=ed[i].ne){
if(ed[i].to==f) continue;
int v=ed[i].to;
dis[v]=dis[no]-dis[v]-son[v]+n-son[v]+dis[v];
if(dis[v]<dis[id]||(dis[v]==dis[id]&&v<id)){
id=v;
ans=dis[v];
}
dfss(ed[i].to,no);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;++i){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,0);
ans=dis[1];
id=1;
dfss(1,0);
cout<<id<<" "<<ans;
return 0;
}