树形dp解决树上选点问题

解题思路:

1、根据输入数据，构建树。双亲表示法，一个列表L，L[i]有两项：【双亲、权重】

2、根据题意，应该用动态规划法，就对树分层，找到每层的结点有哪些。根是第一层。我们遍历每一个结点，回溯到根，计算得到该节点的层数，存入layer_node列表，layer_node[i]是个列表，存储第i层所有的结点编号。假设一共有N层。

3、到状态转移方程了，最难的地方。

dp是个n*2的数组，用列表表示。

dp[i][0]:表示设结点i在第x层，那么从根到第2层、第3层。。。。第x-1层，然后到结点i，如果不选结点i时，此时选中的所有结点的最大权值

dp[i][1]:表示设结点i在第x层，那么从根到第2层、第3层。。。。第x-1层，然后到结点i，如果选结点i时，此时选中的所有结点的最大权值

还是选和不选的问题。

如果不选结点i，那么从第x-1层的每个结点j对应的dp[j][0]/dp[j][1]怎样推导得到dp[i][0]呢？是x-1层所有结点的max(dp[j][0]/dp[j][1])

如果选结点i，那么从第x-1层的每个结点j对应的dp[j][0]/dp[j][1]怎样推导得到dp[i][0]呢？

是或者跳过第x-1层所有结点，此时为max(dp[j][0])+结点i的权值；或者路径来自x-1层一个结点，这个结点最理想的是x-1层的dp[][1]的最大值，但如果其恰好是结点i的双亲结点，就冲突了，那只能选择第二大值。

由于是从根到最后一层推导，因此我们从最后一层中找dp[][0]/dp[][1]中的最大的即可。

注意事项:
构建树、找到每层的结点是基本功。

参考代码:

n=int(input())

L=[[-1,0] for i in range(n+1)] #存储每个结点的【双亲编号，权】

L2=list(map(int,input().split()))

j=2

for i in range(len(L2)):        

    L[j][0]=L2[i] #父节点

    j+=1

L3=list(map(int,input().split()))

j=1

for i in range(len(L3)):        

    L[j][1]=L3[i] #结点权值

    j+=1

#找到每一层的结点

#有多少层呢？最多n层

layer_node=[[] for i in range(n+1)]

layer_node[1]=[1]

for i in range(2,n+1):

    h=2

    j=i

    while L[j][0]!=1:

        h+=1

        j=L[j][0]

    layer_node[h].append(i)

for i in range(1,n+1):

    if layer_node[i]==[]:

        break

#[1,i-1]层有结点，第i层是叶子结点

#print(layer_node)

dp=[[-1,-1] for i in range(n+1)]

#dp[i][0]存储从根层到结点i，不选取i时，已有序列的最大值

#dp[i][1]存储从根层到结点i，选取i时，已有序列的最大值

#这样从前到后推，最后一层中保存的最大值才是最终要找的

dp[1]=[0,L[1][1]]

for x in range(2,i):

    #第x层

    #对x层的每个结点k，都要找dp[k][0]\dp[k][1]

    #对于x-1层的每个结点j，若（j,k)是边，要注意互斥条件，

    #若不是边，就简单得多就选取dp[j][0]\dp[j][1]中最大值+k的权值

    #找到第x-1层中，dp[][0]最大值，dp[][1]最大、次大值

    #

    dp0max=-1

    dp1max1=dp1max2=[-1,-1]

    if len(layer_node[x-1])>1:    

        for j in layer_node[x-1]:

            if dp[j][1]>dp1max1[1]:

                dp1max2=dp1max1

                dp1max1=[j,dp[j][1]]

            elif dp[j][1]>dp1max2[1]:

                dp1max2=[j,dp[j][1]]

            if dp[j][0]>dp0max:

                dp0max=dp[j][0]

    else:

        j=layer_node[x-1][0]

        dp1max1=[j,dp[j][1]]

        dp1max2=[j,0]

        dp0max=dp[j][0]

    for k in layer_node[x]:

        dp[k][0]=max(dp0max,dp1max1[1])

        dp[k][1]=max(dp0max,dp1max1[1])+L[k][1]

        j=dp1max1[0]

        if L[k][0]==j:#j是k的双亲结点

            dp[k][1]=max(dp0max,dp1max2[1])+L[k][1]

        #print(dp,k)

        #print(dp,k,j)

#print(dp)

ans=0    

for j in layer_node[i-1]:

    ans=max(ans,dp[j][0],dp[j][1])

print(ans)

后记：

怎样找到每层结点的dp[][1]中的最大和次大值，这部分代码显得有些啰嗦，看着很不爽。。。。。