树形状态转移
定义f[i][1]为当前节点已选的快乐指数总和最大, f[i][0]为不选当前节点的快乐指数总和最大
我们会发现f[i][1] 可以由f[s][0]推出
f[i][0] 可以由f[s][1], f[s][0]推出
接下来枚举
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
int h[N], e[N], ne[N], w[N], idx;
bool father[N];
int f[N][2];
inline void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
inline void dfs(int u)
{
f[u][1] = w[u];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
int cnt = f[j][0] > f[j][1] ? f[j][0] : f[j][1];
f[u][0] += cnt;
f[u][1] += f[j][0];
}
}
inline void solve()
{
int n;
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i < n; i ++ )
{
int l, k;
cin >> l >> k;
father[l] = true;
add(k, l);
}
int root = 1;
while (father[root]) root ++;
dfs(root);
int cnt = f[root][0] > f[root][1] ? f[root][0] : f[root][1];
cout << cnt << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}