有 N N 个点，每个点有一个价值AiAi。它们之间由 N−1 N − 1 条边，边不会形成环，即两个宝藏点之间有且只有一条通路。探险队有 M M 个人，从点1出发，每次可以留一个人在此点开采宝藏，也可以不留，然后其余的人可以分成若干队向这一点相邻的点走去。 如果他们把队伍分成两队或两队以上，就必须留一个人在当前点，提供联络和通讯，当然这个人也可以一边开采此地的宝藏。并且，为了节约时间，队伍在前往开采宝藏的过程中是不会走回头路的。现在你作为队长的助理，已经提供了这幅藏宝图，请你算出探险队所能开采的最大宝藏的价值。 1≤n≤100，1≤m≤1001≤n≤100，1≤m≤100
不难想到树形dp： 设f[i][j]表示对以 i i 为根的子树中，我们下放了jj个人得到的最大收益。 当在 i i 时不分组的话，显然， f[i][j]=maxf[i][j]=max{ f[Soni][j] f [ S o n i ] [ j ] }，将这个作为 f[i][j] f [ i ] [ j ] 的初值 当在 i i 时分组的话，显然在根ii需要留下一个人，则要分 i−1 i − 1 个人下去， 那么我们对每个 Soni S o n i 枚举一个下放人数 k k f[i][j]=maxf[i][j]=max{ f[Soni][k]+f[i][j−k−1]+a[i] f [ S o n i ] [ k ] + f [ i ] [ j − k − 1 ] + a [ i ] } 因为 f[i][j] f [ i ] [ j ] 会被更新，这样 f[i][j−k−1] f [ i ] [ j − k − 1 ] 就会变，而且我们并不知道 f[i][j−k−1] f [ i ] [ j − k − 1 ] 是否已经计算过 a[i] a [ i ] 那么我们可以 设 g[i][j] g [ i ] [ j ] 表示以i位根的子树中，我们下放了 j j 个人并且第ii处并没有留人得到的最大收益来解决这个问题， 即将 f[i][j]=max f [ i ] [ j ] = m a x { f[Soni][k]+f[i][j−k−1]+a[i] f [ S o n i ] [ k ] + f [ i ] [ j − k − 1 ] + a [ i ] } 转化成 f[i][j]=max f [ i ] [ j ] = m a x { f[Soni][k]+g[i][j−k−1]+a[i] f [ S o n i ] [ k ] + g [ i ] [ j − k − 1 ] + a [ i ] } 在维护完 f[i][j] f [ i ] [ j ] 以后将 g[i][j] g [ i ] [ j ] 维护一下即可 时间复杂度: O(N3) O ( N 3 )
