派对最大快乐值

import sys
[n, root] = [int(x) for x in input().split()]
happyV = [int(x) for x in input().split()]
tree = [[] for x in range(n+1)]
for line in sys.stdin:
    [u,v] = [int(x) for x in line.split()]
    tree[u].append(v)

ishave = [-1 for x in range(n+1)]
nothave = [-1 for x in range(n+1)]

def search(current):
    #if ishave[current] != -1:
        #return (ishave[current], nothave[current])
    if tree[current].__len__() == 0:#说明是叶子结点，即没有下级，直接添加快乐值
        ishave[current] = happyV[current-1]
        nothave[current] = 0
        return (ishave[current], nothave[current])

    isH = happyV[current-1]# 本节点快乐值
    notH = 0
    for xi in tree[current]:
        (isHi, notHi) = search(xi)
        isH += notHi #当前节点的快乐值+下一分支中不包含分支根节点的快乐值
        notH += max(isHi, notHi) #不含当前节点的快乐值+ 下一分支的最大快乐值

    ishave[current] = isH
    nothave[current] = notH

    return (ishave[current], nothave[current])

(Ishave, Nothave) = search(root)
print(max(Ishave, Nothave))
'''
import sys
[n,root] = [int(x) for x in input().split()]
happy = [int(x) for x in input().split()]
tree = [[] for i in range(n+1)]
for line in sys.stdin:
    [u,v] = [int(x) for x in line.split()]
    tree[u].append(v)
isHave = [-1 for i in range(n+1)]
notHave = [-1 for i in range(n+1)]
def search(x):
    if isHave[x] != -1:
        return (isHave[x], notHave[x])
    if tree[x].__len__() == 0:
        isHave[x] = happy[x-1]
        notHave[x] = 0
        return (isHave[x], notHave[x])
    isH = happy[x-1] 
    notH = 0
    for xi in tree[x]:
        (isHi,notHi) = search(xi)
        isH += notHi
        notH += max([isHi, notHi])
    isHave[x] = isH
    notHave[x] = notH
    return (isHave[x], notHave[x])
(isH, notH) = search(root)
print(max([isH, notH]))
'''

本人的代码是参考下面的代码之后写出来的，基本上是一样的，只是有一点不同，就是search里面的第一个if语句，我的代码是注释掉的。

解题关键在于： 注意题目中的条件1，如果某个员工来了，那么这个员工的所有直接下级都不能来。这表明在添加子节点分支计算快乐值得时候，需要判断是否加入本节点。注意到这一点之后，就可以想到，每一个节点都有两个快乐值和，一个是包含本节点的快乐值和ishave，另一个是不包含本节点的快乐值和nothave。另外快乐值得累加也需要注意，在计算本节点的快乐值的时候，也需要注意遵循如果某个员工来了，那么这个员工的所有直接下级都不能来，具体的方法参看search函数，有点词穷，不知道怎么说明。

关于search中的第一个if语句，我个人的理解是防止同一个节点（员工）被计算两次导致重复计算，但是我认为树形结构不会出现一个节点有多个父节点的情况，所以注释了，实际提交的时候也通过了。

第一次写思路，希望大家多指点！！