AT_KeioPC2025_g Treasure Collection

给定一个有 $N$ 个顶点、每个顶点编号为 $1$ 到 $N$ 的有向图。该图的第 $i$ 条边是从顶点 $i$ 指向顶点 $X_i$ 的有向边。保证如果忽略边的方向，将该图看作无向图时该图是连通的。 每个顶点上放置有一些棋子，其中顶点 $i$ 上有 $A_i$ 个棋子。你将进行如下操作共 $N$ 次： - 将所有棋子，沿着它们所在顶点唯一的一条出边移动到下一个顶点。 对于 $k=0,1,\dots,N$，请你求出每次操作结束后，$\sum_{i=1}^N (\text{顶点 } i \text{ 上棋子的个数}) \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$ 的顺序，用空格分隔输出每次操作结束后的答案。

## 部分分 本题设置部分分。 - 若你能正确解决存在某个 $i$ 使得 $X_i = i$ 的数据集，可得 $1$ 分。 ## 样例解释1 $(\text{顶点 }1\text{ 上棋子的个数},\text{顶点 }2\text{ 上棋子的个数},\text{顶点 }3\text{ 上棋子的个数})$ 的变化如下： - $(4,1,2) \rightarrow (3,4,0) \rightarrow (4,3,0) \rightarrow (3,4,0)$ 每一时刻的 $\sum_{i=1}^N (\text{顶点 }i\text{ 上的棋子个数}) \times B_i$ 分别是 $19,29,27,29$。 # 数据范围 - $1 \le N \le 2 \times 10^5$ - $1 \le X_i \le N$ - $1 \le A_i,B_i \le 10^6$ - 保证输入的有向图忽略方向后连通 - 所有输入均为整数 由 ChatGPT 5 翻译