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)。$

【其他输入输出样例】

其他输入输出样例下载

注意：样例2约束与3-6一致

    样例3约束与9-10一致

    样例4约束与11-14一致

    样例5约束与17-20一致

【数据规模与约定】

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

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

【题目来源】

NOI2021 Day1 Task1