答案会比你想象的简单很多

题目链接

这道题最大的障碍应该是猜对题意。。。题里说的“possibility”应该不是真正的相对于人数的概率，而是可以随意相加的数字，你可以直接当成获得这个数量的金币之类的。

树形迷宫，只要你能放置超过对应数量的士兵在这个节点，你就可以获得这个节点的“possibility”。同时你可以继续向这个节点的子节点进行进攻，你甚至可以兵分几路向下前进。这些被放置的士兵只能留在被放置的节点而不能重复利用。你一共有m个士兵，求出你可以获得的“possibility”的最大值。

正向思考

每当你占领一个节点，面临的就是你如何要用剩下的军队，分成几部分去这个节点的子节点。显然正向出发去求你并不知道到底怎样决策才能获得最大价值，因为你甚至还不知道接下来你会面临什么样的节点。

反向思考

这就要搬出和深搜常绑定的一个词——“回溯”。我们一路深搜到叶子节点，我们要从终点走到起点。面对只有一个节点，你当然知道你最少需要多少士兵，你最大能获得多少价值。我们用dp[x][i]表示第x节点用掉i个士兵获得的最大的价值。如果当前节点最少需要j个士兵，那么dp[x][j～m]的初始值就是当前节点的价值量。毕竟人少了不行，但是人多了是肯定可以的。

当两个叶子汇聚到一个父节点应该怎么转移呢？我们需要就将人分成两部分，一部分x个人给一个叶子，一部分y个人给另一个（或者另好几个）叶子，父节点用的人数就是x+y+i个人。因为我们已经知道了每个节点用多少人能够获得多少价值，我们可以枚举所有情况来进行更新最优解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
const int mxlen = 110;
int pre[mxlen*2],last[mxlen],other[mxlen*2],l;

void add(int x,int y){
    l++;
    pre[l] = last[x];
    last[x] = l;
    other[l] = y;
}

int n,m;
int dp[mxlen][mxlen];
bool vis[mxlen];
int bugs[mxlen],brains[mxlen];
void prepare(){
    l = 0;
    memset(pre,0,sizeof(pre));
    memset(last,0,sizeof(last));
    memset(other,0,sizeof(other));
    memset(dp,0,sizeof(dp));
    memset(vis,false,sizeof(vis));
}

void dfs(int x){
    vis[x] = true;
    // 向上取整
    int needed = (bugs[x]+19)/20;
    for(int i=needed;i<=m;i++){
        dp[x][i] = brains[x];
    }
    for(int p=last[x];p;p=pre[p]){
        int y = other[p];
        if(vis[y]) continue;
        dfs(y);
        for(int i = m;i>=needed;i--){
            for(int j=1;j<=i-needed;j++){
                //第x节点消耗i个士兵能获得的最大价值
                dp[x][i] = max(dp[x][i],dp[x][i-j]+dp[y][j]);
            }
        }
    }
}

int main(){
    while(1){
        scanf("%d%d",&n,&m);
        if(n==-1&&m==-1) break;
        prepare();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&bugs[i],&brains[i]);
        }
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        if(m==0){
            cout<<0<<endl;
            continue;
        }
        dfs(1);
        cout<<dp[1][m]<<endl;
    }

    return 0;
}