树形dp
(树形dp) $O(n)$
跟打家劫舍那种很像啊,只是说可能性变成了邻接表而不是固定的
时间复杂度
n,每个点走了一次
C++ 代码
// 树形dp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6010;
int ne[N], e[N], h[N], idx = 0; // 邻接表
int Happy[N]; // 快乐指数
int n;
bool father[N];
int chose[N], uchose[N];
void add(int x, int y)
{
e[idx] = x; ne[idx] = h[y]; h[y] = idx ++;
}
void dp(int m)
{
chose[m] = Happy[m];
// 顺着来的,每个点只执行了一次
for(int i = h[m]; i != -1; i = ne[i])
{
dp(e[i]); // e[i]节点值
chose[m] += uchose[e[i]];
uchose[m] += max(chose[e[i]], uchose[e[i]]);
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++)
cin >> Happy[i];
for(int i = 1; i < n; i ++)
{
int x, y;
cin >> x >> y;
father[x] = true; // x是有上司的
add(x, y); // x加入y的邻接表
}
for(int i = 1; i <= n; i ++)
if(!father[i])
{
dp(i);
cout << max(chose[i], uchose[i]);
break;
}
return 0;
}