poj 3107 Godfather（樹形dp）

題目鏈接：  poj-3107     題意    給一顆n個結點的樹，節點編號為1~n，問刪除一個節點之後，讓剩下的分支中節點數量最多的盡量少。    可能有多種方案，按編號順序輸出。     思路    簡單的樹形dp. 其實連dp都不能算吧...就是直接計數統計    先dfs計算每個節點子樹的節點個數tot[i]。    再次dfs更新答案：    f[i] = max( n-tot[i], max{tot[v] | v是i的兒子} );    兩個dfs可以合並在一個dfs裡完成, 復雜度O(n)       代碼

   
/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : poj-3107 Godfather
 *   @description : 樹形dp
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/08/30 16:26 All rights reserved. 
 *======================================================*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

typedef pair<int, int >PII;
typedef long long int64;
const int INF = 0x3f3f3f3f;

const int MAXN = 50010;
int tot[MAXN];
int f[MAXN], minx;

namespace Adj {
    int size, head[MAXN];
    struct Node{
        int v, next; 
    }E[MAXN*2];
    inline void initAdj() {
        size = 0;
        memset(head, -1, sizeof(head));
    }
    inline void addEdge(int u, int v) {
        E[size].v = v;
        E[size].next = head[u];
        head[u] = size++;
    }
}
using namespace Adj;

int n;

int dfs(int u, int fa) {

    tot[u] = 1;
    // count
    for (int e = head[u]; e != -1; e = E[e].next) {
        int v = E[e].v;
        if (v == fa) continue;
        tot[u] += dfs(v, u);
    }
    // 計算答案
    int& ans = f[u] = n - tot[u];
    for (int e = head[u]; e != -1; e = E[e].next) {
        int v = E[e].v;
        if (v == fa) continue;
        ans = max(ans, tot[v]);
    }
    minx = min(minx, ans);
    return tot[u];
}

int main(){

    while (~scanf("%d", &n)) {

        initAdj();
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }

        minx = INF;
        dfs(1, -1);

        bool first = true;
        for (int i = 1; i <= n; ++i) 
            if (f[i] == minx) {
                if (first) first = false, printf("%d", i);
                else printf(" %d", i);
            }
        puts("");
    }
    return 0;