很经典的一道树形dp题目
先放下代码,后面补题解。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int v[N], tot, head[N], dp[N][2], cnt[N];
struct Edge{
int v, next;
}edge[N];
void add(int u, int v){
edge[tot].next = head[u];
edge[tot].v = v;
head[u] = tot ++;
}
void dfs(int now){
dp[now][0] = 0;
dp[now][1] = v[now];
for(int i = head[now]; i != -1; i = edge[i].next){
int v = edge[i].v;
dfs(v);
dp[now][0] += max(dp[v][0], dp[v][1]);
dp[now][1] += dp[v][0];
}
}
int main(){
int n;
cin >> n;
memset(head, -1, sizeof head);
for(int i = 1; i <= n; i ++)
cin >> v[i];
for(int i = 1; i <= n - 1; i ++){
int u, v;
cin >> u >> v;
add(v, u);
cnt[u] = 1;
}
int node;
for(int i = 1; i <= n; i ++)
if(cnt[i] == 0)
node = i;
dfs(node);
cout << max(dp[node][0], dp[node][1]) << endl;
return 0;
}