poj 2378 Tree Cutting（樹形dp）

本文出自   http://blog.csdn.net/shuangde800

--------------------------------------------------------------------------------------

題目連結：  poj-2378

題意

     給一顆n個結點的樹，節點編号為1~n，把删除一個節點之後，

     剩下的分支中節點數量最多的數量不大于總數量一半的編号全部按順序輸出

思路

     和poj-3107 GodFather完全一樣，隻是輸出不一樣。改為<=n/2的就輸出即可。

代碼

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : poj-2378 Tree Cutting
 *   @description : 樹形dp
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/08/31 14:10 All rights reserved. 
 *======================================================*/
#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
         using namespace std; typedef pair
        
         PII; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 10010; 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); } dfs(1, -1); for (int i = 1; i <= n; ++i) if (f[i] <= n/2) { printf("%d\n", i); } puts(""); } return 0; }