一. 题目
二. 思路
树形DP,关注点还是最优子结构,即父亲并不关心儿子怎么求,只需知道儿子是最优解即可
三. 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=6e3+10, M=2;
int n;
int a[N];
class SingleLinkedList
{
public:
int h[N], e[N], ne[N], idx;
public:
SingleLinkedList()
{
initIO();
idx=0;
fill(h, h+N, -1);
fill(e, e+N, 0);
fill(ne, ne+N, 0);
}
void initIO()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
}
void add(int a, int b)
{
e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
}sll;
class DP
{
public:
int f[N][M];
bool st[N];
public:
DP()
{
fill(&f[0][0], &f[0][0]+N*M, 0);
fill(st, st+N, false);
}
void dfs(int u)
{
f[u][1]=a[u];//当前选
for(int i=sll.h[u];~i;i=sll.ne[i])
{
int j=sll.e[i];
dfs(j);
f[u][0]+=max(f[j][0], f[j][1]);
f[u][1]+=f[j][0];
}
}
}dp;
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<n;++i)
{
int a, b;
cin>>a>>b;
sll.add(b, a), dp.st[a]=true;
}
int root=1;
while(dp.st[root]) ++root;
dp.dfs(root);
cout<<max(dp.f[root][0], dp.f[root][1]);
}