A6581. 「NOI2021」轻重边
编程题
省选/NOI-
知识点
题目描述
小 W 有一棵 $n$ 个结点的树，树上的每一条边可能是轻边或者重边。接下来你需要对树进行 $m$ 次操作，在所有操作开始前，树上所有边都是轻边。操作有以下两种：
1. 给定两个点 $a$ 和 $b$，首先对于 $a$ 到 $b$ 路径上的所有点 $x$（包含 $a$ 和 $b$），你要将与 $x$ 相连的所有边变为轻边。然后再将 $a$ 到 $b$ 路径上包含的所有边变为重边。
2. 给定两个点 $a$ 和 $b$，你需要计算当前 $a$ 到 $b$ 的路径上一共包含多少条重边。
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$。
edge.in 中读入数据。本题有多组数据，输入数据第一行一个正整数 $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$ 类操作，输出一行一个整数表示答案。
edge.out 中。对于每一次第 $2$ 类操作，输出一行一个整数表示答案。
输入输出样例
输入 #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
1 3 2 1