题目链接：http://poj.org/problem?id=3107
求树的重心，所谓树的重心就是：在无根树转换为有根树的过程中，去掉根节点之后，剩下的树的最大结点最小，该点即为重心。
剩下的数的 最大结点dp[i]=max(max(s[j]),n-s[i]) 其中的s[i]为以i为根节点的子树的结点总数，j为i的孩子。
//思路和代码都是比较好理解的
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=5e4+;
const int INF=0x3f3f3f3f; struct Edge
{
int v;
int next;
} edge[maxn<<]; int dp[maxn];
int s[maxn];
int head[maxn];
int n,k; void init()
{
k=;
memset(head,-,sizeof(head));
} void addedge(int u,int v)
{
edge[k].v=v;
edge[k].next=head[u];
head[u]=k++; edge[k].v=u;
edge[k].next=head[v];
head[v]=k++;
} void dfs1(int u,int p)
{
s[u]=;
for(int i=head[u]; i!=-; i=edge[i].next)
{
int v=edge[i].v;
if(v==p) continue;
dfs1(v,u);
s[u]+=s[v];
}
} void dfs2(int u,int p)
{
for(int i=head[u]; i!=-; i=edge[i].next)
{
int v=edge[i].v;
if(v==p) continue;
dp[u]=max(dp[u],s[v]);
dfs2(v,u);
}
dp[u]=max(dp[u],n-s[u]);
} int main()
{
while(scanf("%d",&n)==)
{
init();
int a,b;
for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
}
memset(dp,,sizeof(dp));
dfs1(,-);
dfs2(,-);
int ans=INF;
for(int i=; i<=n; i++)
if(dp[i]<ans) ans=dp[i];
int flag=;
for(int i=; i<=n; i++)
{
if(dp[i]==ans)
{
if(flag==)
{
printf("%d",i);
flag=;
}
else
printf(" %d",i);
}
}
printf("\n");
}
return ;
}
poj1655 题目链接：http://poj.org/problem?id=1655
求树的重心，输出重心和结点最少的树的结点数。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=5e4+;
const int INF=0x3f3f3f3f; struct Edge
{
int v;
int next;
} edge[maxn<<]; int dp[maxn];
int s[maxn];
int head[maxn];
int n,k; void init()
{
k=;
memset(head,-,sizeof(head));
} void addedge(int u,int v)
{
edge[k].v=v;
edge[k].next=head[u];
head[u]=k++; edge[k].v=u;
edge[k].next=head[v];
head[v]=k++;
} void dfs1(int u,int p)
{
s[u]=;
for(int i=head[u]; i!=-; i=edge[i].next)
{
int v=edge[i].v;
if(v==p) continue;
dfs1(v,u);
s[u]+=s[v];
}
} void dfs2(int u,int p)
{
for(int i=head[u]; i!=-; i=edge[i].next)
{
int v=edge[i].v;
if(v==p) continue;
dp[u]=max(dp[u],s[v]);
dfs2(v,u);
}
dp[u]=max(dp[u],n-s[u]);
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
for(int t=; t<=T; t++)
{
scanf("%d",&n);
init();
int a,b;
for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
}
memset(dp,,sizeof(dp));
dfs1(,-);
dfs2(,-);
int ans=INF,k;
for(int i=; i<=n; i++)
if(dp[i]<ans) k=i,ans=dp[i];
printf("%d %d\n",k,ans);
}
return ;
}