POJ3107-God father(树形dp？？)

最新推荐文章于 2021-02-14 14:20:00 发布

drrrrrrrrr

最新推荐文章于 2021-02-14 14:20:00 发布

阅读量267

点赞数

分类专栏： poj训练计划文章标签：树形dp dp

本文链接：https://blog.csdn.net/acm513828825/article/details/78344558

版权

poj训练计划专栏收录该内容

27 篇文章

订阅专栏

原题链接:http://poj.org/problem?id=3107

Godfather

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 6121		Accepted: 2164

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

Sample Output

2 3

Source

Northeastern Europe 2005, Northern Subregion

题目大意:

求树的重心,就是删除一个节点i之后,假设剩下的k个子树中的结点数为(a1,a2,...aj,..ak) 我们取max( a[1....k] )就是取a(1~k)中的最大的那个数,假设为aj,题目的要求就是求一个i使aj最小.

思路:

说是树形dp..起始我觉得更像是树形dfs,dp的思想倒是没有感受到多少,dfs一遍树记录每个以当前结点为根的子树的结点数保存下来;

因为删除结点i之后,剩下的树只有两种,1.原树删除以i为根的子树剩下的树,2.删除i之后新形成的子树

所以我们只需要比较这几颗树,找出其中拥有结点最多的一棵树,保存其结点树就可以了,为方便叙述,假设当前结点为u;i结点的结点数为num[i];v为u的儿子结点;

即 1.min=max(son of (u),min) 2.min=max(min,n-num[v]);

代码如下

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Max(a, b) a>b?a:b
using namespace std ;
const int MAX = 50001 ;
int vis[MAX], head[MAX], ans[MAX], num[MAX] ;
int n, k, Min, sum ;
struct Edge{
    int v, next ;
}edge[2*MAX] ;
void addedge(int a, int b){
    edge[k].v = b ;
    edge[k].next = head[a] ;
    head[a] = k ++ ;
}
void dfs(int x){
    int i, v, min = -1 ;
    num[x] = 1 ;
    vis[x] = 1 ;
    for(i=head[x]; i; i=edge[i].next){
        v = edge[i].v ;
        if(vis[v])  continue ;
        dfs(v) ;
        num[x] += num[v] ;//计算节点数
        min = Max(min, num[v]) ;//选取子树中节点最多的
    }
    min = Max(min, n-num[x]) ;//子树中较大者与除去root为x的树相比较
    if(min<Min){
        Min = min ;
        sum = 1 ;
        ans[0] = x ;
    }else if(min==Min){
        ans[sum++] = x ;
    }
}
int main(){
    int x, y ;
    scanf("%d", &n) ;
    k = 1 ;
    memset(head, 0, sizeof(head)) ;
    for(int i=1; i<n; i++){
        scanf("%d%d", &x, &y) ;
        addedge(x, y) ;
        addedge(y, x) ;
    }
    memset(num, 0, sizeof(num)) ;
    memset(vis, 0, sizeof(vis)) ;
    Min = MAX ;
    dfs(1) ;
    sort(ans, ans+sum) ;
    for(int i=0; i<sum; i++)
        printf("%d ", ans[i]) ;
    printf("\n") ;
    return 0 ;}