树形动态规划中，如何确定树的重心（Godfather）？

本文共计1253个文字，预计阅读时间需要6分钟。

近年来，芝加哥充斥着帮派冲突和离奇的谋杀案。警方高层对此深感疲惫，决定逮捕黑帮头目。不幸的是，芝加哥黑帮结构相当复杂。

Last years Chicago was full of gangster fights and strange murders. The chief of the police got really tired of all these crimes, and decided to arrest the mafia leaders.

Unfortunately, the structure of Chicago mafia is rather complicated. There are n persons known to be related to mafia. The police have traced their activity for some time, and know that some of them are communicating with each other. Based on the data collected, the chief of the police suggests that the mafia hierarchy can be represented as a tree. The head of the mafia, Godfather, is the root of the tree, and if some person is represented by a node in the tree, its direct subordinates are represented by the children of that node. For the purpose of conspiracy the gangsters only communicate with their direct subordinates and their direct master.

Unfortunately, though the police know gangsters’ communications, they do not know who is a master in any pair of communicating persons. Thus they only have an undirected tree of communications, and do not know who Godfather is.

Based on the idea that Godfather wants to have the most possible control over mafia, the chief of the police has made a suggestion that Godfather is such a person that after deleting it from the communications tree the size of the largest remaining connected component is as small as possible. Help the police to find all potential Godfathers and they will arrest them.

Input

The first line of the input file contains n — the number of persons suspected to belong to mafia (2 ≤ n ≤ 50 000). Let them be numbered from 1 to n.

The following n − 1 lines contain two integer numbers each. The pair a_i, b_i means that the gangster a_i has communicated with the gangster b_i. It is guaranteed that the gangsters’ communications form a tree.

Output

Print the numbers of all persons that are suspected to be Godfather. The numbers must be printed in the increasing order, separated by spaces.

Sample Input

6
1 2
2 3
2 5
3 4
3 6

Sample Output

2 3

题目大概：

有一颗由n个点组成的无根树，找出它的所有重心。

思路：

首先树重心是什么。

树的重心是，与重心相连的所有子树中，结点数最多的子树 是所有节点的最多子树中最少的。

然后遍历一边树就可以了，在遍历的时候求一下每个节点的最大子树，也比较求出最少的节点数。

最后在最后输出符合条件的节点即可。

刚开始的时候用的vector，因为初步估计不会超时，但是vector是真心慢，5000的数据量都超时了，

最后改用结构体，数组来实现。

代码：

ac代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int n;
int d[50005];
int dp[50005];
int head[50005];
int minshu;
int ans;
struct shu
{
int v;
int next;
}tr[100005];
void add(int q,int w)
{
tr[ans].v=w;
tr[ans].next=head[q];
head[q]=ans++;

}
void dfs(int x,int pa)
{
d[x]=1;
int maxshu=-1000000;
for(int i=head[x];i!=-1;i=tr[i].next)
{
int son=tr[i].v;
if(son!=pa)
{
dfs(son,x);
d[x]+=d[son];
maxshu=max(maxshu,d[son]);
}
}
dp[x]=max(maxshu,n-d[x]);
minshu=min(dp[x],minshu);

}
int main()
{

while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
memset(d,0,sizeof(d));
memset(head,-1,sizeof(head));
ans=0;
for(int i=1;i<n;i++)
{
int q,w;
scanf("%d%d",&q,&w);
add(q,w);
add(w,q);
}

minshu=10000000;
dfs(1,-1);
for(int i=1;i<=n;i++)
{
if(dp[i]==minshu)
{
printf("%d ",i);
}
}

printf("\n");
}
return 0;
}

vector tle代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int n;
vector<int>tr[50005];
int d[50005];
int dp[50005];
int minshu;
int minx;
void dfs(int x,int pa)
{
d[x]=1;
int maxshu=0;
for(int i=0;i<tr[x].size();i++)
{
int son=tr[x][i];
if(son!=pa)
{
dfs(son,x);
d[x]+=d[son];
maxshu=max(maxshu,d[son]);
}
}
dp[x]=max(maxshu,n-d[x]);
minshu=min(dp[x],minshu);

}
int main()
{

while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
memset(d,0,sizeof(d));
for(int i=1;i<n;i++)
{
tr[i].clear();

}

for(int i=1;i<n;i++)
{
int q,w;
scanf("%d%d",&q,&w);
tr[q].push_back(w);
tr[w].push_back(q);
}

minshu=10000000;
minx=0;
dfs(1,0);

for(int i=1;i<=n;i++)
{
if(dp[i]==minshu)
{
printf("%d ",i);
}
}

printf("\n");
}
return 0;
}