<span>HDU3107 Godfather（树的重心）</span>
题意：
给你一棵树，求树的所有重心并按字典序输出
思路：
树形dp找一遍，把重心记到一个数组里，最后sort一下
这个题用vector居然超时。。。。。。
这让习惯用vector的人瞬间感觉就不好了。。
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=5e4+10; int n,sum[N],ans[N],p,l; bool vis[N]; int head[N],r; struct wq { int v,next; }eg[N<<1]; void add(int u,int v) { eg[r].v=v; eg[r].next=head[u]; head[u]=r++; } void dfs(int u) { int ma=0; sum[u]=0; vis[u]=1; for(int i=head[u];~i;i=eg[i].next) { int v=eg[i].v; if(vis[v]) continue; dfs(v); sum[u]+=sum[v]+1; ma=max(ma,sum[v]+1); } ma=max(ma,n-sum[u]-1); if(ma<p) { p=ma; l=0; ans[l++]=u; } else if(ma==p) ans[l++]=u; } int main() { //freopen("in.txt","r",stdin); int x,y; while(~scanf("%d",&n)) { l=0; r=0; p=inf; memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1); sort(ans,ans+l); for(int i=0;i<l;i++) printf("%d%c",ans[i],i==l-1?'\n':' '); } return 0; }
