/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MB
問題文
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 行目には, 辺の長さの情報 L_2, L_3, ..., L_N が空白区切りで与えられる.
4 行目には, 店の種類の情報 R_1, R_2, R_3, ..., R_N が空白区切りで与えられる. R_i は, 頂点 i の店の種類を表す.
出力
i 行目には, 頂点 i の不便さを 1 行で出力せよ.
注意
入力サイズが 1 ケース当たり 7.5 MB 程度と大きいので, C++ の場合 cin/cout ではなく scanf/printf を使うことが推奨される.
制約
- 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 に含まれる.
writer: E869120