#NOI2021A. 轻重边 (Light and Heavy Edges)

轻重边 (Light and Heavy Edges)

题目描述

小 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\ne b_i

输出格式

输出到文件 edge.out 中。 对于每一次第 22 类操作,输出一行一个整数表示答案。

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

11 次操作,重边有:(1,3)(1, 3)(3,6)(3, 6)(6,7)(6, 7)
22 次操作,包含的重边有:(1,3)(1, 3)
33 次操作,包含的重边有:(1,3)(1, 3)(3,6)(3, 6)(6,7)(6, 7)
44 次操作,首先 (1,3)(1, 3)(3,6)(3, 6) 变为轻边,之后 (1,3)(1, 3)(3,5)(3, 5) 变为重边。
55 次操作,包含的重边有:(1,3)(1, 3)(6,7)(6, 7)
66 次操作,首先 (1,3)(1, 3) 变为轻边,之后 (1,2)(1, 2) 变为重边。
77 次操作,包含的重边有:(6,7)(6, 7)

样例 2

见附加文件 edge2.inedge2.ans

该样例约束与测试点 363\sim 6 一致。

样例 3

见附加文件 edge3.inedge3.ans

该样例约束与测试点 9109\sim 10 一致。

样例 4

见附加文件 edge4.inedge4.ans

该样例约束与测试点 111411\sim 14 一致。

样例 5

见附加文件 edge5.inedge5.ans

该样例约束与测试点 172017\sim 20 一致。

数据规模与约定

对于所有测试数据:T3T\le 31n,m1051\le n,m\le 10^5

测试点编号 n,mn,m\le 特殊性质
121\sim 2 100100
363\sim 6 50005000
787\sim 8 10510^5 A,B\text{A,B}
9109\sim 10 A\text{A}
111411\sim 14 B\text{B}
151615\sim 16 2×1042\times 10^4
172017\sim 20 10510^5

特殊性质 A\text{A}:树的形态是一条链。
特殊性质 B\text{B}:第 22 类操作给出的 aia_ibib_i 之间有边直接相连。