关于黑白树的近10条评论(全部评论)
真的神仙题，$10^6$ 卡树剖，卡LCT ┭┮﹏┭┮ 2024-02-07 19:08 2楼
神仙题，弃了弃了，鬼知道这么大数据在卡谁 Hale 2019-08-28 08:57 1楼

3229. 黑白树

★★★ 输入文件：bzoj_3319.in 输出文件：bzoj_3319.out 简单对比
时间限制：1 s 内存限制：512 MiB

给定一棵树，边的颜色为黑或白，初始时全部为白色。维护两个操作：

1.查询 $u$ 到根路径上的第一条黑色边的标号。

2.将 $u$ 到 $v$ 路径上的所有边的颜色设为黑色。

Notice:这棵树的根节点为1

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

接下来n-1行，每行2个数$u,v$.表示一条 $u$ 到 $v$ 的边。

接下来m行，每行为以下格式：

1 v 表示第一个操作

2 v u 表示第二种操作

$ n，m<=10^6$

对于每个询问，输出相应答案。

如果不存在，输出0

5 4

1 2

1 3

2 4

2 5

1 2

2 2 3

1 3

1 4

BZOJ 3319