Description
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 ai, bi means that the gangster ai has communicated with the gangster bi. 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
题意：给你一颗树，问删除哪个点会使得剩下的连通块中的最大值最小？如果有多少个点符合，按递增顺序输出。
题解：树形DP，枚举每个点，删除它，然后记录剩下的连通块的最大值（剩下的连通块为它的子树和它的父节点），最后进行比较即可，点只会为1个或者2个（当树对称的时候为2个）。
PS:用vector会超时，要改成其他的储存树。
第一次用前向星，看着注释也挺好理解的。
//树形DP+前向星
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 50005
#define inf ((1<<30)-1)
#define max(a,b) ((a)>(b)?(a):(b))
int n;
int dp[MAX];
int num[MAX];
int edge[MAX<<1];//表示第i条边的终点
int next[MAX<<1];//与第i条边同起点的下一条边的位置
int head[MAX<<1];//以i为起点的第一条边的储存位置
vector<int> out;
void insert(int i,int a,int b)//a起点,b终点
{
edge[i]=b;
next[i]=head[a];
head[a]=i;
}
void dfs(int x,int pre)
{
int summ=0,k;
dp[x]=0;
num[x]=1;
for(int i=head[x];i!=-1;i=next[i])
{
k=edge[i];
if(k!=pre)
{
dfs(k,x);
summ+=num[k];
dp[x]=max(dp[x],num[k]);//处理孩子结点的情况
}
}
num[x]=summ+1;
dp[x]=max(dp[x],n-summ-1);//处理父结点的情况
}
int main()
{
int a,b;
for(;~scanf("%d",&n);)
{
memset(num,0,sizeof(dp));
memset(next,-1,sizeof(next));
memset(head,-1,sizeof(head));
memset(edge,-1,sizeof(edge));
for(int i=1;i<=2*(n-1);i+=2)
{
scanf("%d%d",&a,&b);
insert(i,a,b);
insert(i+1,b,a);
}
dfs(1,-1);
int ans=inf;
for(int i=1;i<=n;++i)
if(dp[i]<ans)
{
ans=dp[i];
out.clear();
out.push_back(i);
}
else if(dp[i]==ans)
out.push_back(i);
sort(out.begin(),out.end());
for(int i=0;i<out.size();++i)
if(i==0) printf("%d",out[i]);
else printf(" %d",out[i]);
printf("\n");
}
return 0;
}