f[i][0/1] 表示以i为根节点的子树当选择i或者不选择i时的最大快乐值
对于f[i][1] 也就是我们选择 i 所以进入dfs 我们先将w[i] 加入 f[i][1] 中，然后，我们对于 i 各个孩子，我们都不能取 （因为不能有直接上司）,所以我们加 f[j][0]（也就是说我们加上不取 j 的时候最大快乐值）
对于f[i][0] 也就是我们不选择 i 所以我们可以 1.取子树 f[j][1] 2 . 不取子树 f[j][0] , 两者之间取最大值
#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std ; const int N = 6010 ; vector<int> tree[N] ;//存邻接表 int f[N][2] ;//表示以i为结点的子树，当取i 或着 不取i时 的最大快乐值 int has_fa[N] ;//记录每一个点是否有父节点，方便找根节点 int n ; int w[N] ;//每一个节点的快乐值 void dfs(int u){ f[u][1] = w[u] ; for(int i = 0 ; i < tree[u].size() ; i ++){ int j = tree[u][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 >> w[i] ; for(int i = 1 ; i < n ;i ++){ int a , b ; cin >> a >> b ; tree[b].push_back(a) ; has_fa[a] = 1 ; } int root = 1 ; while(has_fa[root]) root ++ ; dfs(root) ; printf("%d\n",max(f[root][0],f[root][1])) ; return 0 ; }
