| 题目名称 | 2115. [SPOJ 2666] QTREE4 |
|---|---|
| 输入输出 | QTREE4.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 4000 ms (4 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mikumikumi
于2016-02-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：32， 提交：135， 通过率：23.7% | ||||
 dashgua |
100 | 1.778 s | 18.34 MiB | C++ |
 Fmuckss |
100 | 1.989 s | 49.52 MiB | C++ |
 AntiLeaf |
100 | 2.119 s | 83.66 MiB | C++ |
|
AntiLeaf |
100 | 2.212 s | 141.27 MiB | C++ |
 FoolMike |
100 | 2.295 s | 139.55 MiB | C++ |
 jacky_yang |
100 | 2.471 s | 153.47 MiB | C++ |
 MistyEye |
100 | 2.613 s | 65.35 MiB | C++ |
 mikumikumi |
100 | 2.906 s | 85.16 MiB | C++ |
 ONCE AGAIN |
100 | 2.939 s | 84.05 MiB | C++ |
 Vergil |
100 | 3.046 s | 115.76 MiB | C++ |
| 关于 QTREE4 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
和捉迷藏区别在哪里？？？又一次cdq分治水掉
FoolMike
2017-07-11 15:26
6楼
| ||||
|
| ||||
|
这份代码其实有错......(以1为根建树就会WA......)
让我慢慢调...... UPD：COGS数据太弱了......我到vjudge上怎么交都WA...... UPD：改成点分治过了......然而vjudge上TLE到死...... | ||||
|
听说边分治比较慢.. 专门去学习了一个
| ||||
|
那 QTREE 5, 6, 7 呢？催更。
| ||||
|
著名的Qtree系列。
| ||||
【题目描述】
一棵树上有黑白两种颜色的点，树上每条边都有边权。树上的点最初都为白色，现在我们需要维护两种操作。
1.C操作，把编号为x的点的颜色翻转。
2.A操作，查询最远的两个白点的距离
【输入格式】
第一行一个整数N，代表点的个数(N<=100000)；
之后的N-1行，每行三个整数x,y,z代表x和y之间存在一条边权为z的边（-1000<=z<=1000)
之后是一个Q，代表有Q个操作。
接下来的Q行，每行有为一个C操作或一个A操作
【输出格式】
对于每个A操作，输出最远的两个白点的距离，如果树上没有白点，输出They have disappeared.
【样例输入】
3 1 2 1 1 3 1 7 A C 1 A C 2 A C 3 A
【样例输出】
2 2 0 They have disappeared.