acwing 285 没有上司的舞会 2022/05/11_xl上司

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 6010 ;
int happy[N] ;
int e[N] , h[N] , ne[N] , idx ;
bool hasfather[N];
int f[N][2];
int n;
 
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 != -1 ; i = ne[i])
    {
        int j = e[i] ;
        dfs(j) ;
        
        f[u][0] += max(f[j][1] , f[j][0]) ;
        f[u][1] += f[j][0] ;
    }
}
int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin>> happy[i] ;
    }
    memset(h , -1 , sizeof h) ;
    for(int i = 1 ; i < n ; i++)
    {
        int a , b ;
        cin >> a  >> b ;
        hasfather[a] = true ;
        add(b,a);
    }
    int root = 1;
    while(hasfather[root]) root ++ ;
    dfs(root);
    int res = max(f[root][0] , f[root][1]) ;
    cout << res ;
    return 0 ;
}