TOJ 2676 ZOJ 3201 Tree of Tree / 树形DP

时间限制(普通/ Java):1000MS/10000MS 运行内存限制:65536KByte

描述

You're given a tree with weights of each node, you need to find the maximum subtree of specified size of this tree.

Tree Definition

A tree is a connected graph which contains no cycles.

输入

There are several test cases in the input.

The first line of each case are two integers N(1 <= N <= 100), K(1 <= K <= N), where N is the number of nodes of this tree, and K is the subtree's size, followed by a line with N nonnegative integers, where the k-th integer indicates the weight of k-th node. The following N - 1 lines describe the tree, each line are two integers which means there is an edge between these two nodes. All indices above are zero-base and it is guaranteed that the description of the tree is correct.

输出

One line with a single integer for each case, which is the total weights of the maximum subtree.

样例输入

3 1

10 20 30

0 1

0 2

3 2

10 20 30

0 1

0 2

样例输出

30

40

说真的 树形DP不会 参考别人 找些题目练练 熟悉一下这个类型

#include   
#include   
#include   
#define MAX 110  
using namespace std;  
int a[MAX];  
int dp[MAX][MAX];  
bool vis[MAX];  
vector  v[MAX];  
int n,m;  
int max(int x,int y)  
{  
    return x>y x:y;  
}  
void dfs(int u)  
{  
    vis[u] = true;  
    dp[u][1] = a[u];  
    int len = v[u].size(),i,j,k;  
    for(i = 0;i < len; i++)  
    {  
        if(vis[v[u][i]])  
            continue;  
        dfs(v[u][i]);  
        for(j = m; j >= 1; j--)  
        {  
            for(k = 1; k <= j; k++)  
            {  
                dp[u][j] = max(dp[u][j],dp[u][k] + dp[v[u][i]][j-k]);  
            }  
        }  
    }  
}  
int main()  
{  
    int i,x,y;  
    while(scanf("%d %d",&n,&m)!=EOF)  
    {  
        for(i = 0; i < n; i++)  
        {  
            v[i].clear();  
            scanf("%d",&a[i]);  
        }  
        for(i = 1; i < n; i++)  
        {  
            scanf("%d %d",&x,&y);  
            v[x].push_back(y);  
            v[y].push_back(x);  
        }  
        memset(dp,0,sizeof(dp));  
        memset(vis,false,sizeof(vis));  
        dfs(0);  
        int ans = 0;  
        for(i = 0;i < n; i++)  
        {  
            if(ans < dp[i][m])  
                ans = dp[i][m];  
        }  
        printf("%d\n",ans);  
    }  
    return 0;