| 题目名称 | 2281. [HZOI 2015]白黑树 |
|---|---|
| 输入输出 | C_Tree.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 5 |
| 题目来源 |
 Aglove
于2016-04-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：20， 提交：30， 通过率：66.67% | ||||
 AntiLeaf |
100 | 0.261 s | 7.37 MiB | C++ |
|
AntiLeaf |
100 | 0.269 s | 7.36 MiB | C++ |
 Vergil |
100 | 0.276 s | 22.42 MiB | C++ |
 assassain |
100 | 0.288 s | 17.48 MiB | C++ |
|
AntiLeaf |
100 | 0.293 s | 21.10 MiB | C++ |
 FoolMike |
100 | 0.306 s | 22.22 MiB | C++ |
 Sky_miner |
100 | 0.311 s | 28.71 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.312 s | 40.19 MiB | C++ |
|
AntiLeaf |
100 | 0.323 s | 21.10 MiB | C++ |
|
AntiLeaf |
100 | 0.336 s | 21.10 MiB | C++ |
| 关于 白黑树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题有一个log的做法，虽然常数不太占优势，跟两个log的跑起来差不多……
| ||||
|
link-cut-tree上套个二分就行了，两个log而已。
这也是本SB写的首道link-cut-tree（那个弹飞绵羊就别算了吧） | ||||
|
本蒟蒻的题解报告，欢迎来踩blog
http://www.cnblogs.com/joyouth/p/5431139.html  Aglove
2016-04-25 15:31
1楼
| ||||
【题目描述】
给定一棵有根树，树根为1
要求支持以下操作：
1、M u:把u节点反色(即黑色变成白色，白色变成黑色）
2、Q u:查询u和所有黑色节点的所有LCA中深度最小的LCA
【输入格式】
第一行n，m 表示节点总数和操作次数
以下n-1行，每行u，v描述一条边的两个端点
以下m行，每行一个操作，如题意所示
一开始，树上节点都是白色的
n，m<=200000
【输出格式】
对于每个Q询问，如果树上没有黑色节点，输出-1
否则输出对应的答案
【样例输入】
5 5 2 1 3 1 4 1 5 4 Q 5 M 3 Q 3 Q 2 M 1
【样例输出】
-1 3 1