Poj 2378 Tree Cutting (DP_树形DP)

题目大意：给定一棵n棵节点的树，如果删去某个节点使得剩下来的最大分支节点数小等于节点总数的一半则这个删除就是易做图爆的，问易做图爆的删法总数。

解题思路：树形DP.深搜两次，第一次深搜记录从当前节点的子孙节点总数（包括自己）,第一次算预处理，复杂度为O(N),第二次利用第一次的结果找各分支的最大节点数，分支有两种情况，一种是孩子的分支，一种当前节点到父亲节点的那条分支（总数为N-dp[cur])，这样再算N次即可得解。

测试数据：
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

代码：
[html] 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
#define MAX 110000 
#define max(a,b) (a)>(b)?(a):(b) 
 
 
struct node { 
 
    int v; 
    node *next; 
}*head[MAX],tree[MAX]; 
int n,m,ptr,dp[MAX],ans[MAX],cnt; 
 
 
void Initial() { 
 
    cnt = ptr = 0; 
    memset(dp,0,sizeof(dp)); 
    memset(head,NULL,sizeof(head)); 
} 
void AddEdge(int x,int y) { 
 
    tree[ptr].v = y; 
    tree[ptr].next = head[x],head[x] = &tree[ptr++]; 
    tree[ptr].v = x; 
    tree[ptr].next = head[y],head[y] = &tree[ptr++]; 
} 
void Dfs_Ini(int s,int pa) { 
 
    dp[s] = 1; 
    node *p = head[s]; 
    while (p != NULL) { 
 
        if (p->v != pa) { 
 
            Dfs_Ini(p->v,s); 
            dp[s] += dp[p->v]; 
        } 
        p = p->next; 
    } 
} 
void Dfs_Solve(int son,int pa) { 
 
    int i,j,tp,tot = 0; 
    node *p = head[son]; 
     
 
    while (p != NULL) { 
 
        if (p->v != pa) { 
 
            Dfs_Solve(p->v,son); 
            tp = dp[p->v]; 
            tot = max(tot,tp); 
        } 
        p = p->next; 
    } 
    if (n - dp[son] <= n / 2 && tot <= n / 2)  
        cnt++,ans[cnt] = son; 
} 
 
 
int main() 
{ 
    int i,j,k,a,b; 
 
 
    while (scanf("%d",&n) != EOF) { 
 
        Initial(); 
        for (i = 1; i < n; ++i) { 
 
            scanf("%d%d",&a,&b); 
            AddEdge(a,b); 
        } 
 
 
        Dfs_Ini(1,0);           //第一次深搜，记录当前节点的子孙总数 
        Dfs_Solve(1,0);         //更新答案 
        sort(ans+1,ans+1+cnt);  //按字典序输出 
        for (i = 1; i <= cnt; ++i) 
            printf("%d\n",ans[i]); 
        if (cnt == 0) printf("NONE\n"); 
    } 
} 

补充：软件开发 , C语言 ,

上一个：HDU1045
下一个：Poj 1655 Balancing Act (DP_树形DP)