#P11866. [2023年联测]我不是明日方舟玩家
[2023年联测]我不是明日方舟玩家
我不是明日方舟玩家(arknights)
题目描述
你所在的城市是一棵 个点的有根树,其中 号点为根,点 的父节点是,且这条边有 的权值。 在 时刻,你到达了根节点。你想要遍历所有的点,但你将要在 时刻之后离开城市。然而,你可以使用分身术。在任意时刻,你可以产生任意个分身,分身还可以产生分身,且分身可以各自独立地移动。你想要按如下方法遍历整个城市:
如果你或你的分身在 时刻到达点,那么可以选择与 相连的一条边 ,花若干非负整数时间 经过这条边,在 时刻到达点 。 每条边至多被你和你的分身经过 1 次。
如果你或你的分身花了 的时间经过第 条边,那么你会产生 的高兴值。如果你或你的分身在 时刻到达点,那么你会产生 的高兴值。假设产生分身和在一个点上停留的时间忽略不计,你想知道你能产生的高兴值之和最大是多少。 但是你不满足于此。更进一步,你想要知道对于所有 ,如果只考虑以 为根的子树, 且你在 时刻到达点 ,那么你能产生的高兴值之和最大是多少。
输入格式
第一行:两个正整数。
第 行:第 行两个正整数。 第 行: 个正整数 。
输出格式
行,第 行一个数表示 时的答案。
样例输入1
6 10
1 10
1 7
1 6
3 3
2 9
9 19 6 11 1 13 20 1 11 14 20
样例输出1
339
119
59
9
9
9
样例输入2
10 20
1 89
1 75
2 20
1 31
5 69
3 42
6 82
1 21
6 3
582 963 111 463 958 809 757 774 630 522 95 298 723 9 173 131 500 541 189 480 904
样例输出2
14188
1886
2326
582
5043
4096
582
582
582
582
评分方式
如果 的答案正确,则获得 的分数;
如果所有答案都正确,则获得 的分数。
数据范围
$1 \leq n \leq5 \times10^{5} , 1 \leq T \leq5 \times10^{6} , 1 \leq p_{i} < i , 1 \leq w_{i} \leq10^{4} , 1 \leq C_{i} \leq10^{9} .$
对于所有数据,
| 子任务编号 | 分值 | 其他限制 | ||
|---|---|---|---|---|
| 1 | 16 | |||
| 2 | 18 | |||
| 3 | 14 | 随机生成 | ||
| 4 | ||||
| 5 | 18 | |||
| 6 | 20 | |||