http://poj.org/problem?id=3107
树形dp
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 55000 5 using namespace std; 6 const int inf=1<<30; 7 8 int head[maxn],e,n; 9 int dp[maxn]; 10 bool vis[maxn]; 11 int minn; 12 int cnt; 13 int ans[maxn]; 14 struct node 15 { 16 int u,v; 17 int next; 18 }p[maxn*2]; 19 20 void add(int u,int v) 21 { 22 p[e].u=u; 23 p[e].v=v; 24 p[e].next=head[u]; 25 head[u]=e++; 26 } 27 28 void cls() 29 { 30 e=0; 31 cnt=0; 32 memset(ans,0,sizeof(ans)); 33 minn=inf; 34 memset(head,-1,sizeof(head)); 35 } 36 37 void dfs(int u) 38 { 39 int min1=-1; 40 if(vis[u]) return ; 41 vis[u]=true; 42 dp[u]=1; 43 for(int i=head[u]; i!=-1; i=p[i].next) 44 { 45 int v=p[i].v; 46 if(vis[v]) continue; 47 dfs(v); 48 dp[u]+=dp[v]; 49 min1=max(min1,dp[v]); 50 } 51 min1=max(min1,n-dp[u]); 52 if(min1<minn) 53 { 54 cnt=0; 55 ans[cnt++]=u; 56 minn=min1; 57 } 58 else if(min1==minn) 59 { 60 ans[cnt++]=u; 61 } 62 } 63 64 int main() 65 { 66 while(scanf("%d",&n)!=EOF) 67 { 68 cls(); 69 for(int i=1; i<=n-1; i++) 70 { 71 int u,v; 72 scanf("%d%d",&u,&v); 73 add(u,v); 74 add(v,u); 75 } 76 dfs(1); 77 sort(ans,ans+cnt); 78 for(int i=0; i<cnt; i++) 79 { 80 if(i==0) printf("%d",ans[i]); 81 else printf(" %d",ans[i]); 82 } 83 printf(" "); 84 } 85 return 0; 86 }