← 返回题目列表

AtCoder · KeioPC2025_g

G. 宝藏收藏

中文机器翻译题面 查看原题

配点 : 101 点

問題文

在顶部 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 。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le X_i \le N
  • 1 \le A_i,B_i \le 10^6
  • 当将给定图制成忽略边方向的无向图时,该图是连通的。 满足
  • 所有输入均为整数

部分点

针对此问题设置了部分分数。

  • X_i = i 的整数 如果 i 对于现有数据集是正确的 按 1 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

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 的顺序输出答案,并用空格分隔。


入力例 1

3
2 1 1
4 1 2
3 5 1

出力例 1

19 29 27 29 

(頂点 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 。


入力例 2

6
1 6 1 1 4 5
4 4 1 3 3 4
4 2 3 2 2 5

出力例 2

59 66 60 68 76 76 76 

入力例 3

8
3 6 7 5 7 3 6 4
5 1 4 3 5 3 4 4
3 2 5 3 2 3 2 2

出力例 3

81 91 82 96 100 94 96 100 94 

入力例 4

10
2 6 9 5 9 5 6 2 6 6
23957 98539 98777 93417 64636 90740 72538 91432 11805 87997
6580 77845 27752 98108 4695 96373 76155 26842 12878 83118

出力例 4

44227480465 38056928301 30512335897 22545117713 30560451138 30512335897 22545117713 30560451138 30512335897 22545117713 30560451138