该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小 W 有一棵 n 个结点的树,树上的每一条边可能是轻边或者重边。接下来你需要对树进行 m 次操作,在所有操作开始前,树上所有边都是轻边。操作有以下两种:
- 给定两个点 a 和 b,首先对于 a 到 b 路径上的所有点 x(包含 a 和 b),你要将与 x 相连的所有边变为轻边。然后再将 a 到 b 路径上包含的所有边变为重边。
- 给定两个点 a 和 b,你需要计算当前 a 到 b 的路径上一共包含多少条重边。
输入格式
从文件 edge.in
中读入数据。
本题有多组数据,输入数据第一行一个正整数 T,表示数据组数。对于每组数据:
第一行包含两个整数 n 和 m,其中 n 表示结点数量,m 表示操作数量。
接下来 n−1 行,每行包含两个整数 u,v,表示树上的一条边。
接下来 m 行,每行包含三个整数 opi,ai,bi,描述一个操作,其中 opi=1 表示第 1 类操作,opi=2 表示第 2 类操作。
数据保证 ai=bi
输出格式
输出到文件 edge.out
中。
对于每一次第 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 次操作,重边有:(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
见附加文件 edge2.in 与 edge2.ans。
该样例约束与测试点 3∼6 一致。
样例 3
见附加文件 edge3.in 与 edge3.ans。
该样例约束与测试点 9∼10 一致。
样例 4
见附加文件 edge4.in 与 edge4.ans。
该样例约束与测试点 11∼14 一致。
样例 5
见附加文件 edge5.in 与 edge5.ans。
该样例约束与测试点 17∼20 一致。
数据规模与约定
对于所有测试数据:T≤3,1≤n,m≤105。
测试点编号 |
n,m≤ |
特殊性质 |
1∼2 |
100 |
无 |
3∼6 |
5000 |
7∼8 |
105 |
A,B |
9∼10 |
A |
11∼14 |
B |
15∼16 |
2×104 |
无 |
17∼20 |
105 |
特殊性质 A:树的形态是一条链。
特殊性质 B:第 2 类操作给出的 ai 和 bi 之间有边直接相连。