求树的重心。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 50050 #define maxe 100500 using namespace std; struct edge { int v,nxt; }e[maxe]; struct pnt { int id,val; }p[maxv]; int n,x,y,g[maxv],nume=0,size[maxv]; bool cmp(pnt x,pnt y) { if (x.val!=y.val) return x.val<y.val; return x.id<y.id; } void addedge(int u,int v) { e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume; } void dfs(int x,int fath) { size[x]=1;int ret=-0; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=fath) { dfs(v,x); size[x]+=size[v]; ret=max(ret,size[v]); } } ret=max(n-size[x],ret); p[x].id=x;p[x].val=ret; } int main() { scanf("%d",&n); for (int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dfs(1,1); sort(p+1,p+n+1,cmp); int pp=1; printf("%d ",p[pp].id); while (p[pp+1].val==p[pp].val) { printf("%d ",p[pp+1].id); pp++; } printf(" "); return 0; }