经典的有点水的树DP了。。
设S[x]为以节点x为跟的子树的大小。。
画个图便可知去掉x可割出的最大块是他的全体减去他自己的大小和他的最大子树的最大值。。。
P.S
一定要用前向星阿。。
我一直是邻接表的忠实拥护者。。不过这次我受挫了。。
我真不明白，前向星是要排序的。。我用stl是nlogn。。邻接表再怎么垃圾也是O（n）的阿！！。。
怎么一个52ms一个1600+ms。。天阿！！！！
Code。。。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=16000;
int N,cnt=0;
int H[maxn+2]={0};
//graph
struct edge
{
int s,t;
}E[maxn*2];
bool cmp(const edge&x,const edge&y)
{ return x.s<y.s;}
void add(int s,int t)
{
E[cnt].s=s;E[cnt].t=t;cnt++;
E[cnt].s=t;E[cnt].t=s;cnt++;
}
void init()
{
scanf("%d",&N);
int s,t;
for(int i=1;i<N;i++)
{
scanf("%d %d",&s,&t);
add(s,t);
}
sort(E,E+cnt,cmp);
for(int i=0;i<cnt;i++)
H[E[i].s+1]++;
for(int i=2;i<=N+1;i++)
H[i]+=H[i-1];
}
//solve
int ans=maxn+1,acnt=0;
int Ans[maxn+1];
int S[maxn+1]={0};
bool Vis[maxn+1]={0};
int dfs(int x)
{
Vis[x]=true;int Max=0;
for(int i=H[x];i<H[x+1];i++)
{
int o=E[i].t;
if(!Vis[o])
{
S[x]+=dfs(o);
Max=max(Max,S[o]);
}
}   
S[x]++;
Max=max(Max,N-S[x]);
if(Max<ans)   
ans=Max,Ans[0]=x,acnt=1;
else if(Max==ans)
Ans[acnt++]=x;
return S[x];   
}
int main()
{
init();
dfs(1);
cout<<ans<<" "<<acnt<<endl;
sort(Ans,Ans+acnt);
cout<<Ans[0];
for(int i=1;i<acnt;i++)
cout<<" "<<Ans[i];
cout<<endl;
}