题目链接
经典的树形dp,最大独立集,对于每个点就有2个状态,选/不选
设\(dp_{i,0}\)表示不选第i个,\(dp_{i,1}\)表示选第i个,容易得到其状态转移
\(dp_{i,0} = \sum{max(dp_{j,0}, dp_{j,1})}(j为i的儿子节点)\)
\(dp_{i,1} = rating_i + \sum{dp_{j,0}}\)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 6007;
vector<int> son[maxn];
int rating[maxn], in[maxn], dp[maxn][2];
void dfs(int fa) {
for(int i = 0; i < son[fa].size(); ++i) {
int v = son[fa][i];
dfs(v);
dp[fa][0] += max(dp[v][0], dp[v][1]);
dp[fa][1] += dp[v][0];
}
}
void run_case() {
int n;
while(cin >> n) {
if(n == 0) {
cin >> n;
return;
}
for(int i = 1; i <= n; ++i) {
cin >> rating[i];
dp[i][0] = 0;
dp[i][1] = rating[i];
in[i] = 0;
son[i].clear();
}
for(int i = 1; i < n; ++i) {
int u, v;
cin >> v >> u;
in[v]++;
son[u].push_back(v);
}
for(int i = 1; i <= n; ++i)
if(!in[i]) {
dfs(i);
cout << max(dp[i][0], dp[i][1]) << "\n";
break;
}
}
}
int main() {
ios::sync_with_stdio(false), cout.tie(0);
cout.flags(ios::fixed);cout.precision(10);
run_case();
cout.flush();
return 0;
}