問題文
PAKEN王国是, N 它具有顶点的树结构。树顶点 i (2 \leq i \leq N) 是顶点 P_i 和长度 它们通过 L_i 连接。
王国里有文具店、超市等。 M 有不同类型的商店。 1, 2, ..., 種類 M ) 每个顶点都有 1 有个别店,顶 i 有一家商店 有 R_i 。
頂点 i 可以得到第 “不便” 是顶点 i 来自(最近的类型 1 (到存储的最短距离)+(最近的类型 2 (到存储的最短距离)+ ... +(最近的类型 M 定义为到商店的最短距离。
然后,顶点 1, 頂点 2, 頂点 3, ..., 頂点 N 找出每个的不便之处。
入力
输入将以以下格式从标准输入给出。
N M P_2 P_3 ... P_N L_2 L_3 ... L_N R_1 R_2 R_3 ... R_N
1 线上的顶点数 N 和商店类型数量 输入 M ,并用空格分隔。
2 边缘信息在行中 P_2, P_3, ..., P_N 用空格分隔。
3 第 1 行包含边长信息。 L_2, L_3, ..., L_N 用空格分隔。
4 第 1 行包含有关商店类型的信息。 R_1, R_2, R_3, ..., R_N 用空格分隔。 R_i 是顶点 i 代表商店类型。
出力
i 行中,顶点 i 的不便 输出为 1 行。
注意
输入大小为 1 每箱 7.5 MB ,所以在C++中建议使用scanf/printf代替cin/cout。 小于或等于
制約
- N 是 您也可以写 1 以上 400 \ 000 的整数。
- M 是 您也可以写 1 以上 400 \ 000 的整数。
- P_i 是 您也可以写 1 以上 i - 1 的整数。
- L_i 是 您也可以写 1 以上 1 \ 000 \ 000 的整数。
- R_i 是 您也可以写 1 以上 M 的整数。
- 種類 1 减去 M 、各类商店 数量超过 1 。
小課題
小課題1 [ 55点 ]
- N \leq 1 \ 500 很满意。
- M \leq 750 很满意。
小課題2 [ 110点 ]
- N, M \leq 70 \ 000 很满意。
- N = M 很满意。
小課題3 [ 275点 ]
- N, M \leq 70 \ 000 很满意。
- 王国各地有许多相同类型的商店。 只有 8 。
小課題4 [ 330点 ]
- N, M \leq 70 \ 000 很满意。
小課題5 [ 330点 ]
- N, M \leq 400 \ 000 很满意。
入力例1
5 2 1 2 1 2 3 5 2 4 2 1 2 1 1
出力例1
2 3 5 2 7
王国图如下。
入力例2
10 3 1 2 3 3 1 6 7 8 8 2 3 5 3 1 1 6 2 7 1 3 2 2 3 2 3 1 1 3
出力例2
3 5 8 18 11 2 3 13 17 21
王国图如下。
入力例3
5 5 1 2 3 4 1 2 3 4 1 2 3 4 5
出力例3
20 17 15 18 30
这个案例是一个小任务。 包含在 2 中。
作者: E869120