#P3319. 黑白树

    ID: 2506 传统题 1500ms 512MiB 尝试: 992 已通过: 213 难度: 7 上传者: 标签>CF2200提高+/省选-普通并查集逆序处理删除路径压缩按大小合并链表

黑白树

题目描述

给定一棵树,根节点编号为 11,边的颜色为黑或白,初始时全部为白色。维护两个操作:

  • 查询 uu 到根路径上的第一条黑色边的标号。

  • 将 uu 到 vv 路径上的所有边的颜色设为黑色。

输入格式

第一行两个数 n,mn,m,分别表示点数和操作数。

接下来的 n−1n-1 行,每行两个整数 u,vu,v,表示一条 uu 到 vv 的边。

接下来的 mm 行,每行为以下格式:

  • 1 v1\text{ }v 表示第一个操作;

  • 2 v u2\text{ }v\text{ }u 表示第二种操作。

输出格式

对于每个询问,输出相应答案。如果不存在,输出 00。

5 4
1 2
1 3
2 4
2 5
1 2
2 2 3
1 3
1 4
0
2
1

数据规模与约定

对于 100%100\% 的数据,1≤n,m≤1061\leq n,m\leq 10^6。