AT_tkppc3_i 王国と M 種類の店

[problemUrl]: https://atcoder.jp/contests/tkppc3/tasks/tkppc3_i 配点： $ 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 $ 行目には, 辺の長さの情報 $ 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 $ を満たす.