nowcoder multi addrace B

题目描述

给定一内向基环树(base cycle tree)森林。初始时刻每个位置上有一个人，此后，每个时刻都会向前走一步，求所有位置当前人数首次 的时间。

解题思路

对于基环树，极为显然的思路是将环和链分开处理。

首先我们考虑链的答案。假设当前的节点是 ，那么 的子树中， 时刻的答案贡献为深度为 的点的个数。如果每做一个节点都遍历整棵子树，那么超时将在所难免。因此我们考虑将子节点的答案合并至父节点。如果我们选择暴力合并，那么对每个节点都需要新开一个数组，必定会造成空间超限。因此，选择长链剖分的方法，每次将非长链的答案贡献到长链上。

之后我们将得到从环上点出发的长链的答案。我们考虑如何将长链的答案合并到环上。直接求解每个时刻环上点的答案是困难且容易超时的，因此我们考虑每个链上的点对答案的贡献，问题转化为求解链上一点提交到环上时的答案贡献。我们考虑这一贡献的组成，即链上该点的人数，和前一个周期提交位置在环上的前驱节点的人数之和。设提交点为 ，其前驱节点为 ，贡献点为 ，那么答案的贡献即为 。

为了求解所有 的答案，我们考虑维护一个前缀和数组，以初始环上位置为 ，其长链上的深度为 的点作为起点， 位置深度为 的点提交到环上的时间为 ，其对应的 为 % % 。

在得到答案贡献之后，我们扫一遍整条链，即可得到提交点的答案。之后我们再使用二次扫环的方法，对整个环的答案进行更新。

后记

本题的思路较为显然，但是实现过程较为坎坷，调试过程中得到了cxy0x4学长的大力帮助，特此表示感谢。

一个寻找RE位置的方法。

clang++ a.cpp -fsanitize=undefined,address -o a