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

· · 题解

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;

视频题解

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