题解：B4339 [中山市赛 2023] 树的改造

· · 题解

题目传送门

前言

查找最近公共祖先 LCA 和差分找到了这题，然后来水题解。这题好小众。

思路

由于 n \le 10^6，所以时间复杂度为 O(n) 或 O(n \log n)。由于是树上操作，大概率和深度有关，所以时间复杂度应该是 O(n \log n)。然后倍增求 LCA 的思路一眼秒出来了。

给 xxs 做的题不会太难，因为本人也是 xxs。

知道大体算法后，就是先去预处理出每个点的深度 dep_i 和向上跳 2^j 步的落点 father_{i,j}。这段时间复杂度为 O(n \log n)。

然后正常倍增求 LCA，这里就不过多解释了。这段之间复杂度为 O(\log n)。

当 B 树上的边没在 A 树上出现时，显然需要将其路径上的点打一个标记，可以使用一个树上差分，时间复杂度为 O(1)，肯定不会超时。

其中边的判断可以将边的两端点编号通过一些运算计算出哈希唯一值，从而用整型来判断。

然后再跑一边 dfs，把差分数组的前缀和算出来，就可以了。计算答案时，如果差分数组不为零，说明操作过，则答案加 1。

然后输出即可。总时间复杂度 O(n \log n)，面对 10^6 还是绰绰有余的。

AC 记录。

被卡常了，用快读快写！

撒花！