$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路：

1. 建立树，找到该树的根节点 root，并 dfs(root)
2. f[u][0] 表示从以 u 为根节点的子树里面选，不选 u 这个点的最大快乐值
3. f[u][1] 表示从以 u 为根节点的子树里面选，选择 u 这个点的最大快乐值
4. 如果不选 u 这个点，那么它的儿子就可选可不选，f[u][0] += max(f[j][0], f[j][1])
5. 如果选择 u 这个点，那么它的儿子就都不能选，f[u][1] += f[j][0]

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 6010;

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

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

void dfs(int u)
{
    //遍历该点的所有儿子
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]); //不选该点，所以选择该点儿子可选或可不选的最大值
        f[u][1]+=f[j][0]; //选择该点，所以选择该点儿子的不选
    }
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) 
    {
        cin>>happy[i];
        f[i][1]=happy[i]; //选这个点的快乐值
    }

    memset(h,-1,sizeof h);

    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        has_father[a]=true; //该点有根节点
        add(b,a);
    }

    //找到根节点
    int root=1;
    while(has_father[root]) root++;

    dfs(root);

    //选择不选根节点或选根节点的最大快乐值
    cout<<max(f[root][0],f[root][1])<<endl;

    return 0;
}