U189430 带权树形背包

（题目非原创）

你可以理解为每个节点（课程）不光有价值，还有代价的[选课](https://www.luogu.com.cn/problem/P2014)。 给一颗有 $n$ 个节点的树，每个点 $i$ 有重量（代价）$w_j$ 和价值 $v_i$。除根结点外的每个节点必须在其父亲被选择的前提下才能被选择。求在选择的节点重量和不超过 $W$ 的前提下，最大价值和是多少。

第一行两个整数 $n,W$。 接下来 $n-1$ 行每行三个数 $w_i,father_i,v_i$ 根节点的 $father_i$ 在输入中等于自己。

一个整数，表示求在选择的节点重量和不超过 $W$ 的前提下，最大价值和是多少。

### 样例解释 选 $1,2,6$ 号节点。 ### 数据范围 $1 \leq n \leq 5 \times 10^3, \ 1 \leq W, w_i \leq 10^4, \ 1 \leq v_i \leq 10^5, \ 1 \leq father_i \leq max(1, i-1)$ ### 提示 $dfs$ 序优化。