#1854. 「NOI2021」轻重边

「NOI2021」轻重边

题目描述

小 W 有一棵 nn 个结点的树,树上的每一条边可能是轻边或者重边。接下来你需要对树进行 mm 次操作,在所有操作开始前,树上所有边都是轻边。操作有以下两种:

  1. 给定两个点 aabb,首先对于 aabb 路径上的所有点 xx(包含 aabb),你要将与 xx 相连的所有边变为轻边。然后再将 aabb 路径上包含的所有边变为重边。
  2. 给定两个点 aabb,你需要计算当前 aabb 的路径上一共包含多少条重边。

输入格式

从文件 edge.in 中读入数据。

本题有多组数据,输入数据第一行一个正整数 TT,表示数据组数。对于每组数据: 第一行包含两个整数 nnmm,其中 nn 表示结点数量,mm 表示操作数量。

接下来 n1n − 1 行,每行包含两个整数 u,vu,v,表示树上的一条边。

接下来 mm 行,每行包含三个整数 opi,ai,biop_i,a_i,b_i,描述一个操作,其中 opi=1op_i = 1 表示第 11 类操作,opi=2op_i = 2 表示第 22 类操作。

数据保证 aibia_i \neq b_i

输出格式

输出到文件 edge.out 中。

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

样例 1

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)(1, 3)(3,6)(3, 6)(6,7)(6, 7)

第 2 次操作,包含的重边有:(1,3)(1, 3)

第 3 次操作,包含的重边有:(1,3)(1, 3)(3,6)(3, 6)(6,7)(6, 7)

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

第 5 次操作,包含的重边有:(1,3)(1, 3)(6,7)(6, 7)

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

第 7 次操作,包含的重边有:(6,7)(6, 7)

样例 2

见附加文件的 edge/edge2.inedge/edge2.ans

该样例约束与测试点 3 ∼ 6 一致。

样例 3

见附加文件的 edge/edge3.inedge/edge3.ans

该样例约束与测试点 9 ∼ 10 一致。

样例 4

见附加文件的 edge/edge4.inedge/edge4.ans

该样例约束与测试点 11 ∼ 14 一致。

样例 5

见附加文件的 edge/edge5.inedge/edge5.ans

该样例约束与测试点 17 ∼ 20 一致。

测试点约束

对于所有测试数据,有 T3, T \le 3,~1n,m1051 \le n, m \le 10^5

测试点编号 n,mn, m \le 特殊性质
1~2 10
3~6 5000
7~8 10510^5 A, B
9~10 A
11~14 B
15~16 2×1042 \times 10^4
17~20 10510^5

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

特殊性质 B:第 22 类操作给出的 aia_ibib_i 之间有边直接相连