---
# System prepended metadata

title: Untitled

---

```python=
def sol(r, p)
    # dp[i][j] is the maximum reward of select j courses from the subtree which the ith class is the root
    dp = np.zeros([n+1, m+2])
    # set 0 as a dummy root that has 0 reward
    r[0] = 0
    
    def get_dp(x): # get all j of dp[x][j]
        dp[x][0] = 0 # if don't select any node, the sum of reward is 0
        dp[x][1] = r[x] # if only select one node from the subtree, then we can only select the root node
        
        c = child(x) # list of x's child (c[i] is x's ith child)
        # get all the child's dp result 
        for i in range(len(c)):
            get_dp(c[i])
        
        # dp2[i][j] means the maximum reward if we select j child from the first ith child subtree
        dp2 = np.zeros([len(c), m+1]) 
        
        # for dp2[0][j], since we can only select from the 0th child subtree so it is the same as dp[c[0]][j]
        for j in range(m):
            dp2[0][j] = dp[c[0]][j]
        
        
        for i in range(1, len(c)):
            for j in range(m):
                # only select from 0~(i-1) childs
                dp2[i][j] = dp2[i-1][j]
                # select j-k classes from 0~(i-1) childs and k classes from the ith child
                for k in range(1, j+1):
                    if dp2[i][j] < dp2[i-1][j-k] + dp[c[i]][k]:
                        dp2[i][j] = dp2[i-1][j-k] + dp[c[i]][k]
        
        # update dp
        for j in range(2, m+1):
            dp[x][j] = dp2[len(c)-1][j-1] + r[x]
            

    get(0)
    return dp[0][m+1] # m+1 because we have a dummy root

```