【树DP】2021ICPC南京 H

Problem - H - Codeforces
题意：

思路：

这题应该算是铜牌题

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

简单复盘一下思路

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

然后看一下样例：

注意到，对于一个结点 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 longusing 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;
}