Codeforces Round 974 (Div. 3) F. Sheriff‘s Defense（树形DP）

题目链接

Codeforces Round 974 (Div. 3) F. Sheriff’s Defense

思路

我们定义$dp[u][0/1]$表示节点$u$不选或选时，以$u$为根的子树中，郡长能够保留的最多的黄金是多少。

状态转移方程为：

$dp[u][0]+=max(dp[j][0],dp[j][1])(j\in son(u))$。

$dp[u][1]=a[u]+{\sum }_{j\in son(u)}max(dp[j][0],dp[j][1]-c\times 2)$。

最后的答案为：$max(dp[u][0],dp[u][1])$。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, c, ans;
int a[N], dp[N][2];
vector<int>mp[N];
void dfs(int u, int fu)
{dp[u][1] = a[u];for (int j : mp[u]){if (j == fu) continue;dfs(j, u);dp[u][0] += max(dp[j][0], dp[j][1]);dp[u][1] += max(dp[j][0], dp[j][1] - c * 2);}
}
void solve()
{cin >> n >> c;for (int i = 1; i <= n; i++){mp[i].clear();dp[i][0] = dp[i][1] = 0;}for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1, u, v; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs(1, -1);cout << max(dp[1][0], dp[1][1]) << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}