Description

Mitya 和 Vasya 在玩一个有趣的游戏。他们有一颗 $n$ 个节点,以 $1$ 为根的树。除了根之外的每一个节点 $i$,$p_i$ 是它父亲的编号。

对于树的每一个节点 $i$,它包含 $x_i$ 个曲奇,Mitya 需要 $t_i$ 的时间吃掉一块曲奇;在根节点有一块芯片,Mitya 可以花上 $l_i$ 的时间将它移至当前节点的任意一个儿子 $i$ 处。

Mitya 和 Vasya 将轮流进行如下操作(Mitya 先开始):

  • Mitya 将芯片向当前节点的儿子移动;
  • Vasya 切断当前节点到一个儿子的连接。

Mitya 可以在轮到他的时候结束游戏,然后花时间将芯片移回根节点,并且顺路选择性地吃掉一些饼干。我们规定,整个流程(游戏开始到芯片回到根节点)的限时为 $T$。

求出在限定时间内,最坏情况下,Mitya 能吃掉曲奇的最大数量。

Idea

我们从根开始 $DP$,最坏情况就是 Vasya 切断了最优的那个儿子,我们从次优的儿子处转移答案即可,计算答案只要考虑是否在当前节点折返。

我们用树状数组维护沿路上所有曲奇的消耗时间和数量,如果选择在当前节点折返,贪心地选择耗时最小的曲奇吃掉即可,这一步骤可以二分完成。

Code