【树DP】2021ICPC南京 H

待我称王封你为后i 2024-03-24 23:50 78阅读 0赞

[Problem - H - Codeforces][]  
题意：

![2b473d7ad29d4bffbd1d05014beff24f.png][]

思路：

这题应该算是铜牌题

铜牌题 = 简单算法 + 基础思维

简单复盘一下思路

首先，我们发现有个很特殊的条件： ti <= 3

然后看一下样例：

![49a5d1265a5644cc8e4fce844ea7acc0.jpeg][]

注意到，对于一个结点 u ，如果它的所有子节点中没有 tv = 3的，那么就肯定是沿着一棵子树走到底，然后去走剩下的子树

如果所有子节点中有 tv = 3的，那么可以先走到某个子节点，然后再走到这个 tv = 3的结点

注意到了子问题，那么很自然地去考虑树DP

注意到子问题可以分类成不算结点u 和 算结点u， 因此可以这样设计状态

设 dp\[u\] 为没有走过结点 u的这棵子树的贡献

然后考虑转移

因为 ti <= 3， 考虑在转移的时候暴力分讨

因为怎么转移和这些子节点中是否存在 tv = 3的结点有关，那么考虑先去把这些结点遍历一遍，看看是否存在，然后去转移

如果存在，那么就是先走到某个结点，再走到这个tv = 3的结点

考虑枚举这个“某个结点”，注意到tv = 3的结点可能会有多个，我们贪心地保留av最大的那个，这个可以考虑用multiset维护

为了计算贡献，我们设sum\[u\]表示所有子节点的 dp\[v\] 之和

此时的贡献为：

dp\[u\] = max\{sum\[u\] - dp\[v\] + sum\[v\] + a\[v\] + \*rbegin()\}

然后考虑不存在tv = 3的结点，那么就是一次性走到底，再去遍历其他结点，此时贡献为 sum\[u\] + mx，其中 mx 为所有子节点中最大的 a\[v\]

为了防止出问题，我们在原来的multiset中先插入 -Inf

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 1e5 + 10;
    constexpr int M = 1e5 + 10;
    constexpr int P = 2e2 + 10;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    std::vector<int> adj[N];
    
    int n;
    int a[N], t[N];
    int dp[N], sum[N];
    
    void dfs(int u, int fa) {
        std::multiset<int> S;
        int mx = 0;
        for (auto v : adj[u]) {
            if (v == fa) continue;
            dfs(v, u);
            sum[u] += dp[v];
            mx = std::max(mx, a[v]);
            if (t[v] == 3) S.insert(a[v]);
        }
    
        dp[u] = sum[u] + mx;
        S.insert(-0x3f3f3f3f);
    
        for (auto v : adj[u]) {
            if (v == fa) continue;
            if (t[v] == 3) S.erase(S.find(a[v]));
            dp[u] = std::max(dp[u], sum[u] - dp[v] + sum[v] + a[v] + (*S.rbegin()));
            if (t[v] == 3) S.insert(a[v]);
        }
    }
    void solve() {
        std::cin >> n;
        for (int i = 1; i <= n; i ++) {
            sum[i] = dp[i] = 0;
            adj[i].clear();
        }
        for (int i = 1; i <= n; i ++) {
            std::cin >> a[i];
        }
        for (int i = 1; i <= n; i ++) {
            std::cin >> t[i];
        }
    
        for (int i = 1; i <= n - 1; i ++) {
            int u, v;
            std::cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    
        dfs(1, -1);
    
        std::cout << dp[1] + a[1] << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
        std::cin >> t;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - H - Codeforces]: https://codeforces.com/gym/103470/problem/H
[2b473d7ad29d4bffbd1d05014beff24f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/ded4147d8b044bd0b9f1fd250dee019f.png
[49a5d1265a5644cc8e4fce844ea7acc0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9f93d54c4a254ac3a721cbfb83fc461e.png