求表示在满足“大头”的要求的前提下，九头龙的难受值的最小值。如果无法满足要求，输出 −1 − 1 。
1<=N<=300 1 <= N <= 300 ， 2<=M<=N 2 <= M <= N ， 1<=K<=N 1 <= K <= N 。 N个果子依次编号1,2,...,N，最大的果子的编号总是1。 N 个 果 子 依 次 编 号 1 , 2 , . . . , N ， 最 大 的 果 子 的 编 号 总 是 1 。 ( a,b,c a , b , c )为点 a a 到点bb有一条难受值为 c c 的树枝 1<=a<=N1<=a<=N， 1<=b<=N 1 <= b <= N ， 0<=c<=105 0 <= c <= 10 5
无解的情况比较容易判断，即 当 N−K＜M−1 N − K ＜ M − 1 时无解，因为它要分 M M 组，而我们拿掉大头所必须吃掉的KK个后，剩下的至少要 ≥M−1 ≥ M − 1 然后我们讨论一下有解时如何求解，发现可以用树形dp实现， 我们对 M M 分析可以发现， 当M=2M=2时，我们把大头所需要用到的 K K 个消掉，那么剩下了N−KN−K个，而此时 M=1 M = 1 ，则有可能会发生除了大头以外，存在树枝两侧吃掉果实的头相同。 而 M＞2 M ＞ 2 时，则最后剩下的 M−1 M − 1 满足 ≥2 ≥ 2 ，那么我们只需要将剩下的 N−K N − K 给 M−1 M − 1 个头每个都分一份，还剩下 N−K−(M−1) N − K − ( M − 1 ) 个，此时的数量我们可以随便的去分，必定能够与相同的头隔离，即此时存在树枝两侧吃掉果实的头相同的情况仅有大头。 那么我们设 f[i][j][0/1] f [ i ] [ j ] [ 0 / 1 ] 表示以 i i 为根的子树，大头在其中吃了jj颗果实的难受值最小值， 0/1 0 / 1 表示大头是否吃掉了结点 i i 的果实，11是吃了， 0 0 是没吃。 Ai,jAi,j为结点 i i 与结点jj之间树枝的难受值 则不难发现，对于所有的 f[i][0][0]，f[i][1][1] f [ i ] [ 0 ] [ 0 ] ， f [ i ] [ 1 ] [ 1 ] 的初值都是 0 0 而状态转移方程也可以比较容易的推出即，枚举儿子子树中大头吃掉的果实数kk，然后能够得到 对于 f[i][j][1] f [ i ] [ j ] [ 1 ] ： 我们知道此时是大头吃掉了结点 i i 的果实，当儿子结点SoniSoni也是大头吃掉的时候，则累加上难受值，否则就不管，则推得： f[i][j][1]=min f [ i ] [ j ] [ 1 ] = m i n { f[Soni][k][1]+f[i][j−k][1]+Ai,j，f[Soni][k][0]+f[i][j−k][1] f [ S o n i ] [ k ] [ 1 ] + f [ i ] [ j − k ] [ 1 ] + A i , j ， f [ S o n i ] [ k ] [ 0 ] + f [ i ] [ j − k ] [ 1 ] } 而对于 f[i][j][0] f [ i ] [ j ] [ 0 ] ： 我们只需要分类讨论一下 M M 等不等于22即可 M=2 M = 2 ： 儿子不是大头必定就与自己冲突， f[i][j][0]=min f [ i ] [ j ] [ 0 ] = m i n { f[Soni][k][0]+f[i][j−k][0]+Ai,j，f[Soni][k][1]+f[i][j−k][0] f [ S o n i ] [ k ] [ 0 ] + f [ i ] [ j − k ] [ 0 ] + A i , j ， f [ S o n i ] [ k ] [ 1 ] + f [ i ] [ j − k ] [ 0 ] } M＞2 M ＞ 2 ： 儿子必定能够不与自己冲突， f[i][j][0]=min f [ i ] [ j ] [ 0 ] = m i n { f[Soni][k][0]+f[i][j−k][0]，f[Soni][k][1]+f[i][j−k][0] f [ S o n i ] [ k ] [ 0 ] + f [ i ] [ j − k ] [ 0 ] ， f [ S o n i ] [ k ] [ 1 ] + f [ i ] [ j − k ] [ 0 ] }
对于状态转移方程中的 f[i][j−k][0/1] f [ i ] [ j − k ] [ 0 / 1 ] ，因为可能因为 f[i][j][0/1] f [ i ] [ j ] [ 0 / 1 ] 的更新而变化， 所以我们需要实现用一个数组去储存原先 f[i][j] f [ i ] [ j ] 。 时间复杂度: O(N3) O ( N 3 )
