http://poj.org/problem?id=3107
这实际上就是找重心，在之前有做过：http://www.cnblogs.com/qlky/p/5780933.html
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 110000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f int n,m; struct node{int y,val,next;}tree[MAXN<<2]; int head[MAXN],vis[MAXN],ptr=1,dp[MAXN],num[MAXN],ans,tot,a[MAXN]; void init() { mem(head,-1); mem(vis,0); mem(dp,0); ans =INF; tot = 0; ptr=1; } void add(int x,int y) { tree[ptr].y = y; tree[ptr].next = head[x]; head[x] = ptr++; } void dfs(int rt) { num[rt]=vis[rt]=1; int tmp = 0; //pf("rt%d ",rt); for(int i = head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y); num[rt]+=num[y]; tmp = max(tmp,num[y]); //pf("y%d %d ",y,tmp); } tmp = max(tmp,n-num[rt]); //pf("t%d %d %d ",rt,tmp,ans); if(tmp<ans) { ans = tmp; tot = 0; a[tot++] = rt; } else if(tmp == ans) a[tot++] = rt; } int main() { int i,j,k,t; while(~sf("%d",&n)) { init(); for(i=1;i<n;i++) { int x,y; sf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1); sort(a,a+tot); pf("%d",a[0]); for(i=1;i<tot;i++) pf(" %d",a[i]); blank; } }