| 题目名称 | 2286. [HZOI 2015]疯狂的重心 |
|---|---|
| 输入输出 | G_Tree.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-04-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：11， 通过率：63.64% | ||||
 _Horizon |
100 | 0.176 s | 6.80 MiB | C++ |
 一個人的雨 |
100 | 0.178 s | 38.05 MiB | C++ |
 assassain |
100 | 0.206 s | 6.78 MiB | C++ |
 0 |
100 | 0.260 s | 4.81 MiB | C++ |
 stdafx.h |
100 | 0.266 s | 4.51 MiB | C++ |
 Aglove |
100 | 0.283 s | 7.48 MiB | C++ |
 FoolMike |
100 | 0.315 s | 10.59 MiB | C++ |
|
0 |
0 | 0.000 s | 5.35 MiB | C++ |
|
FoolMike |
0 | 0.002 s | 9.83 MiB | C++ |
|
0 |
0 | 0.344 s | 4.81 MiB | C++ |
| 关于 疯狂的重心 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
合并两棵子树后，重心一定在原先的两颗树重心之间，因此在LCT上二分答案就好了。
只想说splay上二分答案细节好多啊…… | ||||
|
http://www.cnblogs.com/joyouth/p/5438373.html
本蒟蒻的题解报告，欢迎各路神犇来踩 Aglove
2016-04-27 12:08
1楼
| ||||
【题目描述】
一开始有n个点，点和点之间没有边，要求你维护以下操作：
1、A u v 在u和v之间添加一条无向边，保证添加后原图还是一个生成森林
2、Q u 询问u所在树的重心的编号
3、Xor 询问所有树的重心的编号的异或和
重心的定义：在一棵树上，若一个点到其他所有点的距离之和最小，则称这个点为树的重心
如果有多个满足条件的点，取编号最小的点为重心
【输入格式】
第一行n，m表示节点总数和操作次数
以下m行每行如题意所示
n,m<=100000
【输出格式】
对于每个Q和Xor输出答案
【样例输入】
10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor
【样例输出】
11
1
1
1
2
6
2