本文共 1256 字，大约阅读时间需要 4 分钟。
题目：
题意：给你一棵树，让你找到结点，使得剩下的联通块中的结点数量最大的尽量小 即树的重心的定义 思路：直接dfs找其子树的max(结点数量,n-结点数量) 这个题卡vector（而且poj竟然不支持auto 代码：#include#include #include #include #include using namespace std;typedef long long ll;const int N = 5e4+5;struct edge{ int to,nxt; edge(int t = 0,int n = 0):to(t),nxt(n){}}E[N*2];int n,tot,head[N*2];int dp[N],num[N],pos[N],cnt,minn;void add_edge(int u,int v){ E[tot] = edge(v,head[u]); head[u] = tot++;}void dfs(int u,int fa){ num[u] = 1; for(int i = head[u];~i;i = E[i].nxt) { int v = E[i].to; if(v == fa) continue; dfs(v,u); num[u] += num[v]; dp[u] = max(dp[u],num[v]); } dp[u] = max(dp[u],n-num[u]); if(dp[u] < minn) { minn = dp[u]; cnt = 0; pos[cnt++] = u; } else if(dp[u] == minn) pos[cnt++] = u;}int main(){ tot = 0; memset(head,-1,sizeof(head)); scanf("%d",&n); int u,v; for(int i = 1;i < n;i++) { scanf("%d%d",&u,&v); add_edge(u,v); add_edge(v,u); } cnt = 0; minn = 50000; dfs(1,-1); sort(pos,pos+cnt); printf("%d",pos[0]); for(int i = 1;i < cnt;i++) printf(" %d",pos[i]); printf("\n"); return 0;}
转载地址：http://bkkgf.baihongyu.com/