| 题目名称 | 2271. [HZOI 2015]黑白树 |
|---|---|
| 输入输出 | AD.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：12， 通过率：50% | ||||
 小一米 |
100 | 1.604 s | 54.10 MiB | C++ |
 FoolMike |
100 | 1.743 s | 105.20 MiB | C++ |
 AntiLeaf |
100 | 2.864 s | 72.03 MiB | C++ |
 神利·代目 |
100 | 2.882 s | 225.55 MiB | C++ |
 Aglove |
100 | 3.417 s | 85.00 MiB | C++ |
 assassain |
100 | 3.759 s | 60.00 MiB | C++ |
 xqz |
0 | 0.733 s | 39.99 MiB | C++ |
 gls1196 |
0 | 1.608 s | 93.63 MiB | C++ |
|
FoolMike |
0 | 1.851 s | 105.20 MiB | C++ |
|
AntiLeaf |
0 | 2.808 s | 71.26 MiB | C++ |
| 关于 黑白树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
本蒟蒻的题解报告，欢迎来踩blog
http://www.cnblogs.com/joyouth/p/5431139.html Aglove
2016-04-25 15:32
1楼
| ||||
【题目描述】
给定一棵有根树，树根为1
要求支持以下三种操作：
1、M u 把u这个节点反色(即白色变成黑色，黑色变成白色）
2、R u 把跟u树上距离为奇数的点反色
3、Q u 查询u和所有黑点的LCA的编号和
【输入格式】
第一行n,m 表示节点数目和操作数目
以下n-1行，每行u，v描述一条边的两个端点，w描述边权
以下m行，每行一个操作如题意所示
注意：一开始树上所有节点均为白色
n，m<=200000,边权<=1000
【输出格式】
对于每个Q操作，输出答案
【样例输入】
5 7 2 1 486 3 2 599 4 1 463 5 4 550 M 2 R 3 M 4 R 2 R 4 Q 4 R 2
【样例输出】
6