3598. [NOI 2021]轻重边

【题目描述】

小 W 有一棵 $n$ 个节点的树，树上的每一条边可能是轻边或者重边。接下来你需要对树进行 $m$ 次操作，在所有操作开始前，树上所有边都是轻边。操作有以下两种：

1. 给定两个点 $a$ 和 $b$，首先对于 $a$ 到 $b$ 路径上的所有点 $x$（包含 $a$ 和 $b$），你要将与 $x$ 相连的所有边变为轻边。然后再将 $a$ 到 $b$ 路径上包含的所有边变为重边。
2. 给定两个点 $a$ 和 $b$，你需要计算当前 $a$ 到 $b$ 的路径一共包含多少条重边。

【输入格式】

本题有多组数据，输入数据第一行一个正整数 $T$，表示数据组数。对于每组数据：

第一行包含两个整数 $n$ 和 $m$，其中 $n$ 表示节点数量，$m$ 表示操作数量。

接下来 $n-1$ 行,每行包含两个整数 $u, v$，表示树上的一条边。

接下来 $m$ 行，每行包含三个整数 ${op}_i,a_i,b_i$，描述一个操作。其中 ${op}_i = 1$ 表示第 $1$ 类操作，${op}_i = 2$ 表示第 2 类操作。

数据保证 $a_i \neq b_i$

【输出格式】

对于每一次第 $2$ 类操作，输出一行一个整数表示答案。

【样例输入】

1
7 7
1 2
1 3
3 4
3 5
3 6
6 7
1 1 7
2 1 4
2 2 7
1 1 5
2 2 7
1 2 1
2 1 7

【样例输出】

1
3
2
1

【样例说明】

第 $1$ 次操作后，重边有：$(1, 3), (3, 6), (6, 7)$。

第 $2$ 次操作，包含的重边有：$(1, 3)$。

第 $3$ 次操作，包含的重边有：$(1, 3), (3, 6), (6, 7)$。

第 $4$ 次操作，首先 $(1, 3), (3, 6)$ 变为轻边，之后 $(1, 3), (3, 5)$ 变为重边。

第 $5$ 次操作，包含的重边有：$(1, 3), (6, 7)$。

第 $6$ 次操作，首先 $(1, 3)$ 变为轻边，之后 $(1, 2)$ 变为重边。

第 $7$ 次操作，包含的重边有：$(6, 7)$。

【其他输入输出样例】

样例下载

注意：

1. 样例 2 约束与 3-6 一致
2. 样例 3 约束与 9-10 一致
3. 样例 4 约束与 11-14 一致
4. 样例 5 约束与 17-20 一致

【数据规模与约定】

特殊性质 $A$：树的形态是一条链

特殊性质 $B$：第 $2$ 类操作给出的 $a_i,b_i$ 之间有边直接相连

【题目来源】

NOI2021 Day1 Task1