题意:

给出一棵节点数为 n 的树，删去一个点 i 的代价为ai，一条链的长度定义为路径上点 的个数。一棵树死了，满足不存在一条长度 >= l 的链，牛牛希望用最少代价杀死这棵树。 n , l <= 5e3

思路：

树上背包。

树上背包最核心的思路就在于：把每一个子树看作一个分组。刷表更新体积.

首先，dp状态很容易想出来。令dp(u , j) 代表点u,向上贡献长为j的链的最少代价。

考虑这样一个事实，对于一个根节点，它的每一个子树只能转移一种长度的链。那么可以把不同长度的链看成是所占的体积，而dp值为价值。那么每一个二元组<不同长度的链,其dp值>就代表着一个物品。那么一颗子树就可以看成是若干个物品，而且只能从这些物品中选取一个物品去转移的模型。这不就是分组背包嘛？每颗子树看作一个新的分组.

考虑新增一颗子树(分组)时，怎么去贡献。 

对于状态转移方程的解释:max(j , k + 1) 的意思是比较j , k 长度，而 j + k < l 显然。两层循环，外层循环j，内层循环k。外层的j代表体积，内层k是k个物品，也就是k种决策。那么这样以来就是一个标准的树上分组背包了.

然后还需要注意一点。外层循环从[1,sizu]  内层循环从[1,sizv].这样一来每两个点都只会在他们的lca处计算一次贡献，保证复杂度O(n^2)