| 题目名称 | 2280. [HZOI 2015]树白黑 |
|---|---|
| 输入输出 | B_Tree.in/out |
| 难度等级 | ★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：22， 提交：42， 通过率：52.38% | ||||
 Sky_miner |
100 | 0.828 s | 94.90 MiB | C++ |
 Vergil |
100 | 0.866 s | 67.43 MiB | C++ |
 AntiLeaf |
100 | 0.919 s | 81.95 MiB | C++ |
 YGOI_真神名曰驴蛋蛋 |
100 | 1.010 s | 73.53 MiB | C++ |
|
AntiLeaf |
100 | 1.037 s | 166.64 MiB | C++ |
|
AntiLeaf |
100 | 1.045 s | 94.15 MiB | C++ |
 FoolMike |
100 | 1.181 s | 363.46 MiB | C++ |
 szzy |
100 | 1.212 s | 94.39 MiB | C++ |
 L_in |
100 | 1.345 s | 114.82 MiB | C++ |
|
AntiLeaf |
100 | 1.394 s | 93.39 MiB | C++ |
| 关于 树白黑 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
一个log跑不过两个log系列
| ||||
|
树剖+二分+树状数组+莫队的n^(3/2)*(logn)^2的试水算法果然过不了上W的数据...
 喵喵喵
2016-12-08 13:33
5楼
| ||||
|
表示没有看懂题QAQ，是要求u和[l,r]的LCA吗？
| ||||
|
本蒟蒻的题解报告，欢迎来踩blog
http://www.cnblogs.com/joyouth/p/5431139.html  Aglove
2016-04-25 15:32
3楼
| ||||
|
回复 @_Horizon :
一时疏忽，没有写上，已更正 Aglove
2016-04-25 15:32
2楼
| ||||
|
这棵树的根是1 QAQ？
 _Horizon
2016-04-25 15:29
1楼
| ||||
【题目描述】
给定一棵有根树，树根为1，一开始这棵树所有节点均为白色
之后给定一个染色序列，第i个数ai表示将ai这个点染黑
之后给定若干询问
询问第L到第R个染黑的黑点和u所有的LCA中深度最大的LCA的编号
【输入格式】
第一行n，m，q 表示节点总数，染色序列长度，询问个数
以下n-1行，每行u，v描述一条边的两个端点
之后m个正整数表示染色序列
之后q行，每行L，R，u 如题目所示
n，m，q<=200000 可能会有点重复被染色
【输出格式】
对于每个询问输出对应的答案
【样例输入】
5 5 5 1 2 2 3 3 4 1 5 3 2 4 3 2 3 5 4 1 2 1 1 1 2 5 5 2 2 2 4
【样例输出】
4 1 2 2 2