AT_KeioPC2025_g Treasure Collection

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ N $ 辺の有向グラフが与えられます。 $ i $ 番目の辺は頂点 $ i $ から頂点 $ X_i $ への辺です。ただし、このグラフは辺の向きを無視した無向グラフにしたときに連結であることが保証されます。 各頂点にはいくつかの駒が置かれており、頂点 $ i $ には $ A_i $ 個の駒が置かれています。あなたはこれから以下の操作を $ N $ 回行います。 - すべての駒を、今置かれている頂点から出ている唯一の辺に沿って移動させる。 $ k = 0,1,\dots,N $ について、 $ k $ 回目の操作が終わった時点での $ \sum_{i=1}^{N} ( $ 頂点 $ i $ に置かれている駒の個数 $ ) \times B_i $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1\ X_2\ \dots\ X_N $ $ A_1\ A_2\ \dots\ A_N $ $ B_1\ B_2\ \dots\ B_N $

$ k = 0,1,\dots,N $ の順に答えを空白区切りで出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ X_i = i $ を満たす整数 $ i $ が存在するデータセットに正解した場合 $ 1 $ 点が与えられる。 ### Sample Explanation 1 $ ( $ 頂点 $ 1 $ に置かれている駒の個数 $ , $ 頂点 $ 2 $ に置かれている駒の個数 $ , $ 頂点 $ 3 $ に置かれている駒の個数 $ ) $ は、以下のように変化します。 - $ (4,1,2) \rightarrow (3,4,0) \rightarrow (4,3,0) \rightarrow (3,4,0) $ それぞれの時点における $ \sum_{i=1}^{N} ( $ 頂点 $ i $ に置かれている駒の個数 $ ) \times B_i $ は、 $ 19,29,27,29 $ です。 ### Constraints - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le X_i \le N $ - $ 1 \le A_i,B_i \le 10^6 $ - 与えられるグラフは辺の向きを無視した無向グラフにしたときに連結 - 入力はすべて整数