题解：CF77C Beavermuncher-0xFF

· · 题解

trick 题，贪心 + dp。

如何发现 dp 性质呢？

答案一定只会从直系儿子直接转移而来，叶子节点可以划分成一个最小的子问题，因此可以 dp。

设计状态 dp_i 表示以 i 为根的子树可以吃掉的海狸的最大数量，那么有：

dp_x = \sum_{u \in x} dp_u

但是发现一个问题，就是如果直接这么转移的话可能不满足限制并且无法很好的处理每个点剩余海狸的数量。

有什么办法可以同时记录两个信息呢，我们联想到可以把 dp 过程改成搜索的形式，在搜索中传入两个参数即可。

在回溯后，记录当前节点儿子的剩余权值的总和和每个 dp 的值。

我们贪心地想，是要选儿子中 dp 值大的那一些。考虑对 dp 排序。

再考虑儿子剩余权值对当前 dp 值的影响。假定一个点 x，那么你可以在 x 和 x 的直系儿子中反复游走，对答案的贡献为：2 \times \min \left \{ rem, sum \right \}，其中 rem 表示 x 的剩余权值，sum 表示 x 的直系儿子权值和。

那么状态转移方程可以大致写为：

dp_x = \sum_{u \in x} dp_u + 2 \times \min \left \{ rem, sum \right \}

转移处的细节较多，具体的可以看代码。

代码：

#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int N = 1e5 + 5;
int n, u, v, rt, a[N];
vector<int> g[N];

inline pi dfs(int x, int last) {
    // first 表示贡献，second 表示剩余权值 

    int sum = 0;
    bool flag = true;
    vector<int> v;

    for(auto u : g[x])
        if(u != last) {
            flag = false;

            pi son = dfs(u, x);

            sum += son.se;
            v.pb(son.fi);
        }

    if(flag) return mp(0ll, a[x] - 1);

    sort(v.begin(), v.end(), greater<int>());

    int res = 0, rem = a[x] - (x != rt);

    for(int i = 0 ; i < (int)v.size() && rem ; ++ i, -- rem)
        res += v[i] + 2;

    // 统计剩余权值贡献 

    res += (min(rem, sum) << 1);
    rem -= min(rem, sum);

//  cout << res << ' ' << rem << '\n';

    return mp(res, rem);
}

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr); 

    cin >> n;
    for(int i = 1 ; i <= n ; ++ i)
        cin >> a[i];
    for(int i = 1 ; i < n ; ++ i) {
        cin >> u >> v;

        g[u].pb(v), g[v].pb(u);
    }
    cin >> rt;

    cout << dfs(rt, -1).fi;

    return 0;
}

/*
3
2 1 1
3 2
1 2
3
*/