ZOJ - 3201 Tree of Tree

ZOJ - 3201 Tree of Tree

題目大意：給一棵節點帶權的樹，找到一個有k個節點的子樹，求這個子樹的最大權值

解題思路：樹形 DP + 背包，f(i, j) 表示以i為根節點的有j個節點子樹的最大權值，然後對i的每個子節點做分組背包，因為對於i的每個兒子，可以選擇分 1,2,3…j-1 個節點給它

f(i, j) = max{ max{f(i, j-p) + f(v, p) | 1 <= p < j} | v是i的兒子節點}
 ans = max{ f[i][k] | 0 <= i < n && i子樹節點個數>=k }

#include 
#include 
#include 
#include 
using namespace std;
int N, K, ans, DP[105][105], vis[105];
vector  A[105];

void init() {
    ans = 0;
    memset(DP, 0, sizeof(DP));
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= N; i++)
        A[i].clear();

    for (int i = 0; i < N; i++)
        scanf("%d", &DP[i][1]);

    int x, y;
    for (int i = 0; i < N - 1; i++) {
        scanf("%d%d", &x, &y);
        A[x].push_back(y);
        A[y].push_back(x);
    }
}

void DPS(int root) {
    vis[root] = 1;
    int num = A[root].size();
    for (int i = 0; i < num; i++) {
        int child = A[root][i];
        if (vis[child])
            continue;
        DPS(child);
        for (int j = K; j > 0; j--)
            for (int r = 1; r < j; r++)
                DP[root][j] = max(DP[root][j], DP[root][j - r] + DP[child][r]);
    }
    ans = max(ans, DP[root][K]);
}

int main() {
    while (scanf("%d%d", &N, &K) != EOF) {
        init();
        DPS(0);
        printf("%d\n", ans);
    }
    return 0;
}