状态表示：
$f[u][1]$表示以u为根节点的子树并且包括u的总快乐指数，
$f[u][0]$表示以u为根节点并且不包括u的总快乐指数;

状态计算：
要想求得一棵以u为根节点的子树的最大指数分为两种：选u节点或不选u节点
记点u的子节点是j
1.选u，$f[u][1] += Σf[j][0]$
2.不选u，$f[u][0] += Σmax(f[j][1] , f[j][0])$

记根节点为root
从root开始dfs一遍即可
最后输出$max(f[root][1] , f[root][0])$

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 6010;

int e[N] , ne[N] , h[N] , idx;
int happy[N];
int n;
bool has_fa[N];
int f[N][2];

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0] , f[j][1]);
    }
}

int main()
{
    cin >> n;

    for(int i = 1 ; i <= n ; i++)    cin >> happy[i];

    memset(h , -1 , sizeof h);

    for(int i = 0 ; i < n - 1 ; i++)
    {
        int a ,b;
        cin >> b >> a;
        has_fa[b] = true;
        add(a , b);
    }

    int root = 1;
    while (has_fa[root]) root ++ ;

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1]));
    return 0;
}