#P11866. [2023年联测]我不是明日方舟玩家

    ID: 11017 传统题 1000ms 512MiB 尝试: 11 已通过: 1 难度: 9 上传者: 标签>计算几何凸包动态规划CF2600树形DP堆数学线段树模拟

[2023年联测]我不是明日方舟玩家

我不是明日方舟玩家(arknights)

题目描述

你所在的城市是一棵nn 个点的有根树,其中 11 号点为根,点ii 的父节点是pip_{i},且这条边有wiw_{i} 的权值。 在00 时刻,你到达了根节点。你想要遍历所有的点,但你将要在TT 时刻之后离开城市。然而,你可以使用分身术。在任意时刻,你可以产生任意个分身,分身还可以产生分身,且分身可以各自独立地移动。你想要按如下方法遍历整个城市:

如果你或你的分身在t0t_{0} 时刻到达点uu,那么可以选择与uu 相连的一条边 (u,v)( u , v ),花若干非负整数时间Δt\Delta t 经过这条边,在t0+Δtt_{0}+\Delta t 时刻到达点 vv。 每条边至多被你和你的分身经过 1 次。

如果你或你的分身花了 Δti\Delta t_{i} 的时间经过第ii 条边,那么你会产生Δti×wi\Delta t_{i} \times w_{i} 的高兴值。如果你或你的分身在tut_{u} 时刻到达点uu,那么你会产生CtuC_{t_{u}} 的高兴值。假设产生分身和在一个点上停留的时间忽略不计,你想知道你能产生的高兴值之和最大是多少。 但是你不满足于此。更进一步,你想要知道对于所有 u=1,2,…,nu=1,2,\ldots,n,如果只考虑以 uu 为根的子树, 且你在 00 时刻到达点 uu,那么你能产生的高兴值之和最大是多少。

输入格式

第一行:两个正整数n,Tn , T。

第2∼n2 \sim n 行:第ii 行两个正整数pi,wip_{i} , w_{i}。 第n+1n+1 行:T+1T+1 个正整数 C0,C1,⋯ ,CTC_{0} , C_{1} , \cdots, C_{T}。

输出格式

nn 行,第ii 行一个数表示u=iu=i 时的答案。

样例输入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

评分方式

如果u=1u=1 的答案正确,则获得 50%50\% 的分数;

如果所有答案都正确,则获得 100%100\% 的分数。

数据范围

$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} .$

对于所有数据,

子任务编号 分值 n≤n \leq T≤T \leq 其他限制
1 16 30003000
2 18 10510^{5} 10510^{5}
3 14 5×1065 \times10^{6} CiC_{i} 随机生成
4 5×1055 \times10^{5} pi=1p_{i}=1
5 18 pi=i−1p_{i}=i-1
6 20