年会题解解解

解题思路:记忆化搜索（深度搜索+动态规划）+树

观察题目发现可以将学校各教职工关系构建成一颗树，由题目限制可得，对于树中任意一个节点都应该有1.自己来，学生不来。2.自己不来，学生来或学生不来两种情况，而对于这两种情况，1=自己的活跃度+学生不来的活跃度。2=各个学生来或者不来分别最大的活跃度之和，因此使用深度优先可以轻松的从叶子节点开始逐步向上直到根节点将1、2两种情况分别求出来。

注意事项:

参考代码:

n=int(input())
happy=[]
lis = [[0] for i in range(n+1)]
dp = [[0]*(3) for i in range(n+1)]//1、2、3分别为当前节点来的情况下与其子树的和，不来的情况下与其子树的和，最大值。
happy.append(0)
for i in range(1,n+1):
   happy.append(int(input()))
while True:
   x,y=map(int,input().split())
   if(x==0 and y==0 ):
       break
   lis[x][0]=y
   lis[y].append(x)
for i in range(1,n+1):
   if(lis[i][0]==0):
       lis[0].append(i)
def DP(param):
   dp[param][1] = 0
   dp[param][0]=0
   for i in range(1,len(lis[param])):
       child=lis[param][i]
       DP(child)
       dp[param][0]+=dp[child][2]//若当前节点不存在，则将其子树的最大值加上，对应第二种情况。
       dp[param][1]+=dp[child][0]//若当前节点存在，则将其子节点不来情况下的子树最大值加上，与下一条语句构成对应第一种情况。
   dp[param][1]+=happy[param]
   if dp[param][0]>=dp[param][1]://判断本节点来与不来那种情况活跃度最大并保存到DP[x][2]
       dp[param][2]=dp[param][0]
   else:
       dp[param][2] = dp[param][1]
DP(0)
print(dp[0][2])