← 返回题目列表

AtCoder · tkppc3_i

I. 王国和M型商店

中文机器翻译题面 查看原题
配点: 1100 点

問題文

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