题面

Kazari 超喜欢刷题。在她眼中，一切题目都可依难度分为三个等级：简单、中等、困难。她最近来到了一个有 $n$ 个节点树形迷宫，树上的每一条双向边都是一道题。

在接下来的 $m$ 天中，第 $i$ 天她会选择 $s_i$ 和 $t_i$ 两点，并从 $t_i$ 走到 $s_i$ 。在走的过程中她必须解决一路上遇到的所有问题。

在每天的开始，Kazari 可以解决任意难度的题目，但是一旦她解决了一道难题后她就会失去信心，并且在这天接下来的时间里只能解决简单题了。

她的执着感动了刷题之神（大雾），于是神在这 $m$ 天中每天会让某一条边上的题目难度变简单一级（困难变成中等，中等变成简单，简单不变），并且这一改变是持久的。

现在 Kazari 想知道对于第 $i$ 天：

1. 她能否从 $t_i$ 到达 $s_i$ ？
2. 在所有节点中，有多少个节点满足：从该节点出发可以到达 $s_i$ ？

数据范围：

$1 \le n, m \le 10^5$

$\sum n, \sum m \le 3 \times 10^5$

题目链接

分析

首先感谢文末提及的参考博文！

树的特性

我们注意到地图是一棵树。

假设 $t$ 和 $s$ 不存在祖先关系，我们考虑在树上从 $t$ 到 $s$ 的过程：

• 首先从 $t$ 出发向上走到达 $t$ 和 $s$ 的某个公共祖先 $a$ ；
• 再从 $a$ 向下走到达 $s$ 。

而如果 $t$ 和 $s$ 存在祖先关系：

• 如果 $s$ 是 $t$ 的祖先，向上走的过程中就到 $s$ 了，省略了第二步；
• 如果 $t$ 是 $s$ 的祖先，直接向下走就可以到 $s$ 了，省略了第一步。

由此我们看到，若 $t$ 和 $s$ 之间可达，那么它们必然拥有共同的祖先。我们不难想到可以用并查集来维护这一属性。

并查集

那么我们不妨维护两个并查集：

• $f_1(x)$ 表示从 $x$ 出发向上只走难度为 $1$ 的边最远可到达的点，也就是维护了难度为 $1$ 的边的连通块；
• $f_2(x)$ 表示从 $x$ 出发向上只走难度为 $1$ 或 $2$ 的边最远可到达的点，也就是维护了难度为 $1$ 和 $2$ 的边的连通块。

另外，我们记录点 $x$ 的父亲为 $\text{father}(x)$ 。

通过这两个并查集，我们甚至可以得知任一条边的难度值。假设已知 $x$ 和 $y$ 间一定存在边，那么如果 $f_1(x) = f_1(y)$ 就说明这条边难度为 $1$ ；如果 $f_1(x) \neq f_1(y)$ 但 $f_2(x) = f_2(y)$ 就说明难度为 $2$ ，如果 $f_1(x) \neq f_1(y)$ 且 $f_2(x) \neq f_2(y)$ 则说明这条边难度为 $3$ 。

怎么初始化这两个并查集呢？首先既然题目给的是一棵无根树我们不妨任选一个点作为根节点然后 DFS，如果遇到某条连接 $x$ 和 $y$ 的边难度为 $1$ ，就在 $f_1$ 和 $f_2$ 里将它们按深度合并，如果难度为 $2$ 就仅在 $f_2$ 里将它们按深度合并。

问题 1

如果 $t$ 可到达 $s$ ，只存在如下三种情况：

• $f_2(t) = f_2(s)$ ：这意味着只走难度为 $1$ 或 $2$ 的边就可从 $t$ 到达 $s$ ；
• $f_1(\text{father}(f_2(t))) = f_1(s)$ ：首先从 $t$ 出发只走难度为 $1$ 或 $2$ 的边最远可到达 $f_2(t)$ 。接下来我们走一条难度为 $3$ 的边到达 $\text{father}(f_2(t))$ ，然后只走难度为 $1$ 的边到达 $s$ ；
• $f_2(\text{father}(f_1(s))) = f_2(t)$ ：考虑到如果 $t$ 是 $s$ 的祖先，应用上面一条规则就会出现问题：我们要走的难度为 $3$ 的边不在 $t$ 的上面而在 $t$ 的下面。因此我们不妨将路径反过来考虑：从 $s$ 出发，开始只能走难度为 $1$ 的边，经过一条难度为 $3$ 的边后就可以走难度为 $1$ 或 $2$ 的边了。如果 $t$ 和 $s$ 不存在祖先关系其实这一条和上一条是等价的。

问题 2

考虑从任意一点 $x$ 可到达 $s$ 的条件（为了方便把路径反过来考虑）：从 $s$ 出发只能走难度为 $1$ 的边，直到遇到并经过了一条难度为 $3$ 的边后只能走难度为 $1$ 或 $2$ 的边，最终到达 $x$ 。

因此我们考虑把答案分为两部分考虑：

• 从 $s$ 出发只经过难度为 $1$ 或 $2$ 的边可到达的点数；
• 从 $s$ 出发先只经过难度为 $1$ 的边，在经过 $1$ 条难度为 $3$ 的边，再经过难度为 $1$ 或 $2$ 的边可到达的点数。

我们对于 $f_1$ 和 $f_2$ 分别维护两个值 $siz_1$ 和 $siz_2$ （注意这两个值都是对于并查集的祖宗而言的）：

• $siz_1(f_1(x))$ 表示从 $f_1(x)$ 往下走，遇到第 $1$ 条难度为 $3$ 的边后只走难度为 $1$ 或 $2$ 的边能到达的点的个数；
• $siz_2(f_2(x))$ 表示以 $f_2(x)$ 为祖宗的并查集的大小。

第一部分的答案，就是 $siz_2(f_2(s))$ 。

下面我们考虑第二部分。我们把第二部分分为两种情况：

• 经过的难度为 $3$ 的边在 $s$ 上方；
• 经过的难度为 $3$ 的边在 $s$ 下方。

对于第二部分的第一种情况，我们从 $s$ 出发向上走，判断第一条难度非 $1$ 的边的难度是否为 $3$ 。如果难度为 $3$ ，我们记经过这条边后所处点为 $k$ ，那么答案就是 $siz_2(f_2(k))$ 。

对于第二部分的第二种情况，就是 $siz_1(f_1(s))$ 。

加起来就好了。

难度更新

记我们需要更新的边两端端点分别为 $x$ 和 $y$ ，且 $\text{depth}(x) < \text{depth}(y)$ 。注意这意味着 $\text{father}(y) = x$ 。

若是从难度为 $3$ 的边降至难度为 $2$ 的边，首先我们在 $f_2$ 中将 $x$ 和 $y$ 合并。此后，我们需要在 $siz_1(f_1(x))$ 中减去 $siz_2(f_2(y))$ ，同时在 $siz_1(f_1(\text{father}(f_1(x))))$ 中加上 $siz_2(f_2(y))$ （至于为什么马上讲）。为了方便，可实现在 $f_2$ 的合并函数中。

因为原先从 $f_1(x)$ 联通块内的点出发可按照 $siz_1$ 定义的方式经过当前这条边到达 $f_2(y)$ 中的点，但现在这条边不复存在，所以需要从 $siz_1(f_1(x))$ 中减去 $siz_2(f_2(y))$ 。而当这条边难度变成 $2$ 时， $f_1(\text{father}(f_2(x)))$ 联通块内的点（$f_2(x)$ 与 $\text{father}(f_2(x))$ 之间的边的难度为 $3$ ）就可以以 $siz_1$ 定义的方式路过这条边到达 $f_2(y)$ 中的点了，所以需要加上 $siz_2(f_2(y))$ 。

若是从难度为 $2$ 的边降至难度为 $1$ 的边，仅在 $f_1$ 中将 $x$ 和 $y$ 合并就可以了。

实现

本题实现起来有点难 QAQ。

完整参考代码

%%%

• 616156 - 【并查集】HDU6334 Problems on a Tree