题目来源：vijos1180. 树形DP，设f[v,num]为以v为根的子树选取num门课所能得到的最大学分。为了方便分配这num门课程，我们将题目所给的多叉树转换为二叉树。 参考资料：原理、代码 .
转为二叉树后，实际上任意节点i的左孩子（包括左孩子的孩子）是i真正的子节点，而i的右孩子（包括右孩子的右孩子）是i节点的兄弟节点。故i未选时，i的所有左孩子不可选，但右孩子可以。于是得状态转移方程如下： 选v时（则左孩子（真正的孩子）可以分配）：
f[v,num]=max(f[v,num],score[v]+f[tree[v,1]],i)+f[tree[v,2],num-i-1]//(0<=i<=num-1)(tree[v,1]即为v的左孩子，tree[v,2]为右孩子)不选v时（只可全给右孩子，即兄弟节点）：
f[v,num]=max(f[v,num],f[tree[v,2]],num)从以上两个方程中取最大值即是解。 觉得写得好的话，就点个赞让我知道一下呗~ AC代码：
program vijos1180; var n,m,i,x:integer; s:array[1..300]of byte;//s means score. tree:array[0..300,1..2]of integer;//1 left,2 right. f:array[1..300,0..300]of integer; function max(a,b:integer):integer; begin if(a>b)then exit(a); exit(b); end; function dp(v,num:integer):integer; var i:integer; begin if(v=0)then exit(0); if(f[v,num]>0)then exit(f[v,num]); for i:=0 to num-1 do f[v,num]:=max( f[v,num], s[v]+dp(tree[v,1],i)+dp(tree[v,2],num-i-1) ); f[v,num]:=max(f[v,num],dp(tree[v,2],num)); exit(f[v,num]); end; begin readln(n,m); for i:=1 to n do begin readln(x,s[i]); if(tree[x,1]>0)then tree[i,2]:=tree[x,1]; tree[x,1]:=i; end;//边读入边转二叉树。 writeln(dp(tree[0,1],m)); end.