树形DP

``` #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); } ```