UOJ Logo Universal Online Judge

UOJ

#673. 【NOI2021】轻重边

附件下载 统计

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

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

输入格式

本题有多组数据,输入数据第一行一个正整数 T,表示数据组数。

对于每组数据: 第一行包含两个整数 nm,其中 n 表示结点数量,m 表示操作数量。

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

接下来 m 行,每行包含三个整数 opi,ai,bi,描述一个操作,其中 opi=1 表示第 1 类操作,opi=2 表示第 2 类操作。

数据保证 aibi

输出格式

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

样例一

input

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

output

1
3
2
1

explanation

第 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)

样例二

见附加文件的 ex_edge2.inex_edge2.ans

该样例约束与测试点 36 一致。

样例三

见附加文件的 ex_edge3.inex_edge3.ans

该样例约束与测试点 910 一致。

样例四

见附加文件的 ex_edge4.inex_edge4.ans

该样例约束与测试点 1114 一致。

样例五

见附加文件的 ex_edge5.inex_edge5.ans

该样例约束与测试点 1720 一致。

测试点约束

对于所有测试数据,有 T3,1n,m105

测试点编号 n,m 特殊性质
12 10
36 5000
78 105 A, B
910 A
1114 B
1516 2×104
1720 105

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

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

时间限制:1s2s

空间限制:1GB