题目详情题解（0）讨论（0）提交记录（0）

AT_KeioPC2025_g.Treasure Collection

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 NN 个顶点、每个顶点编号为 11 到 NN 的有向图。该图的第 ii 条边是从顶点 ii 指向顶点 XiX_i 的有向边。保证如果忽略边的方向，将该图看作无向图时该图是连通的。

每个顶点上放置有一些棋子，其中顶点 ii 上有 AiA_i 个棋子。你将进行如下操作共 NN 次：

  • 将所有棋子，沿着它们所在顶点唯一的一条出边移动到下一个顶点。

对于 k=0,1,…,Nk=0,1,\dots,N，请你求出每次操作结束后，∑i=1N(顶点 i 上棋子的个数)×Bi\sum_{i=1}^N (\text{顶点 } i \text{ 上棋子的个数}) \times B_i 的值。

输入格式

输入以如下格式从标准输入给出。

NN
X1 X2 … XNX_1\ X_2\ \dots\ X_N
A1 A2 … ANA_1\ A_2\ \dots\ A_N
B1 B2 … BNB_1\ B_2\ \dots\ B_N

输出格式

请按 k=0,1,…,Nk=0,1,\dots,N 的顺序，用空格分隔输出每次操作结束后的答案。

输入输出样例

  • 输入#1

    3
2 1 1
4 1 2
3 5 1

    输出#1

    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

说明/提示

部分分

本题设置部分分。

  • 若你能正确解决存在某个 ii 使得 Xi=iX_i = i 的数据集，可得 11 分。

样例解释1

(顶点 1 上棋子的个数,顶点 2 上棋子的个数,顶点 3 上棋子的个数)(\text{顶点 }1\text{ 上棋子的个数},\text{顶点 }2\text{ 上棋子的个数},\text{顶点 }3\text{ 上棋子的个数}) 的变化如下：

  • (4,1,2)→(3,4,0)→(4,3,0)→(3,4,0)(4,1,2) \rightarrow (3,4,0) \rightarrow (4,3,0) \rightarrow (3,4,0)

每一时刻的 ∑i=1N(顶点 i 上的棋子个数)×Bi\sum_{i=1}^N (\text{顶点 }i\text{ 上的棋子个数}) \times B_i 分别是 19,29,27,2919,29,27,29。

数据范围

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤Xi≤N1 \le X_i \le N
  • 1≤Ai,Bi≤1061 \le A_i,B_i \le 10^6
  • 保证输入的有向图忽略方向后连通
  • 所有输入均为整数

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页