#include<bits/stdc++.h>
using namespace std;
struct edge{
int v,next;
}a[100001];
int head[100001];
int siz[50001];
int cnt,ans,maxblock=-1,root,n;
void add(int x,int v)
{
cnt++;
a[cnt].next=head[x];
a[cnt].v=v;
head[x]=cnt;
}
void dfs1(int x)
{
int block=0;
siz[x]=1;
for(int i=head[x];i;i=a[i].next)
{
int v=a[i].v;
if(!siz[v])
{
dfs1(v);
siz[x]+=siz[v];
block=max(block,siz[v]);
}
}
block=max(block,n-siz[x]);
if(block==maxblock)root=min(root,x);
if(block<maxblock||maxblock==-1)
{
maxblock=block;root=x;
}
}
void dfs(int x)
{
siz[x]=1;
for(int i=head[x];i;i=a[i].next)
{
int v=a[i].v;
if(!siz[v])
{
dfs(v);
siz[x]+=siz[v];
}
}
ans+=(siz[x]-1);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);add(x,y);add(y,x);
}
dfs1(1);
memset(siz,0,sizeof(siz));
dfs(root);
printf("%d %d",root,ans);
}
树形DP
2018-07-13 15:11:31