U611930 苹果树

有一棵 $n$ 个点、以 $1$ 为根的有根苹果树，其中 $i$ 号点上有 $a_i$ 个苹果，每取走其中一个苹果就可以得到 $v_i$ 的价值（若在这个结点取走 $k\le a_i$ 个苹果，则可以收获 $kv_i$ 的价值）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。 给定正整数 $k$，请从树上取走若干苹果。如果总计取走了 $t$ 个苹果，且所有取了至少一个苹果的那些结点的最大深度为 $h$（规定根结点的深度为 $1$），则要求 $t−h\le k$. 问最大可以收获多少的价值？

第一行两个整数 $n$ 和 $k$. 接下来 $n$ 行，第 $i$ 行三个整数 $f_i,a_i,v_i$，$f_i$ 表示 $i$ 号点的父节点编号，规定 $f_1=0$.

一行一个整数，表示最大价值。

对于 $10\%$ 的数据，$n\times k\le 3000000$，树的高度为 $2$. 对于 $20\%$ 的数据，$n\times k\le 25000000$，树的高度为 $2$. 对于 $20\%$ 的数据，$n\times k\le 25000000$，$\forall 1\le i\le n,a_i=1$. 对于 $20\%$ 的数据，$n\times k\le 3000000$. 对于 $100\%$ 的数据，$1\le n \le 20000,1\le k\le 500000,1\le n\times k\le 25000000,f_i