TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8417
  • 题目
  • P8417「NOI2021」轻重边
    限制 : 时间限制 : - MS   空间限制 : 1048576 KB
    评测说明 : 1s,1GB
    问题描述

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

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

    输出格式

    对于每一次第 \(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)\)

    数据范围

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

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

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

    特殊性质 B:第 \(2\) 类操作给出的 \(a_i\)\(b_i\) 之间有边直接相连