自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:22，当前版本为作者最后更新于2022-11-27 13:43:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3681 [语言月赛202211] Power Strip 题解

Source & Knowledge

2022 年 11 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

给定 $n$ 个插排的信息，包括插排上连接的充电器数量 $a _ i$ 和插排所连接的上级插排编号 $u _ i$（除 $1$ 号插排外），保证 $u _ i < i$。

对于每个插排，求出其供电的充电器数量。

解析

这里提供一种比较简便的做法。

我们注意到 $u _ i < i$，所以不难发现，第 $i$ 号插排上直接或间接连接的插排的编号一定大于 $i$。换句话说，第 $i$ 号插排供电的充电器一定连接在编号 $\geq i$ 的插排上。

不难想到，如果我们在输出第 $i$ 号插排的信息前，已经计算统计了 $i$ 号插排后面的所有的插排的信息，那么我们一定可以得到 $i$ 号插排完整的供电信息。

其次，我们考虑向前更新的情况。不难发现，我们只需要将第 $i$ 号插排的信息更新到 $u _ i$ 上即可。这样，当我们处理 $u _ i$ 时，将这份信息连带着更新至 $u _ {u _ i}$ 上，以此类推，即可将第 $i$ 号插排的信息更新至所有上游插排。

具体的，我们使用 $f$ 数组记录信息。$f _ i$ 表示第 $i$ 号插排所供电的充电器数量。当我们遍历到 $i$ 号插排时，使 $f _ i$ 增加 $a _ i$，然后让 $f _ {u _ i}$ 增加 $f _ i$ 即可。这样，按照上面的说明，我们在输出前，便得到了 $i$ 号插排的完整信息。

最后输出 $f$ 数组即可。

核心代码：

cin >> n;
for (int i = 2; i <= n; ++i)
	cin >> u[i];
for (int i = 1; i <= n; ++i)
	cin >> a[i];
for (int i = n; i > 1; --i) {
	a[u[i]] += a[i];
}
for (int i = 1; i <= n; ++i)
	cout << a[i] << ' ';
cout << endl;

视频题解

完整代码请在视频中查看。