题目名称	2036. [ZJOI 2007]捉迷藏
输入输出	`hide.in/out`
难度等级	★★★★
时间限制	10000 ms (10 s)
内存限制	512 MiB
测试数据	10
题目来源	mikumikumi 于2015-09-15加入
开放分组	全部用户
提交状态
分类标签	树分治线段树
	分享题解

通过：88，提交：321，通过率：27.41%
KZNS	100	0.971 s	12.46 MiB	C++
PSI	100	0.994 s	41.99 MiB	C++
fye	100	1.025 s	38.37 MiB	C++
PSI	100	1.104 s	36.17 MiB	C++
ceerRep	100	1.152 s	36.26 MiB	C++
TenderRun	100	1.175 s	36.18 MiB	C++
张灵犀不和我一般见识真可怕呢（笑	100	1.176 s	45.33 MiB	C++
mikumikumi	100	1.350 s	45.33 MiB	C++
lcomyn	100	1.391 s	36.65 MiB	C++
thomount	100	1.443 s	50.26 MiB	C++

关于捉迷藏的近10条评论(全部评论)
这谁爱原创谁原创吧，反正我对着题解敲了一遍。瑆の時間~無盡輪迴·林蔭 2020-02-06 03:08 11楼
CSU_Turkey 2018-03-14 17:17 10楼
这题对拍的时候n要小一点才能拍出WA。。。然后修改完了立刻查询。。。 n太大了因为最长链很多条，根本拍不出错。。。给个我拍出错几率较高的生成器（[tab]换成\t）： import random import os def sys(s):return os.system(s) def rand(l,r):return int(random.uniform(l,r+1)) cnt=0 while True: [tab]fout=open("hide.in","w") [tab]n,m=10,10 [tab]orz=[i+1 for i in range(0,n)] [tab]random.shuffle(orz) [tab]print(n,file=fout) [tab]for i in range(2,n+1):print(rand(1,i-1),i,file=fout) [tab]print(m*2,file=fout) [tab]for tjj in range(0,m): [tab][tab]print('C',orz[tjj],file=fout) [tab][tab]print('G',file=fout) [tab]fout.close() [tab]sys("./hide && ./std") [tab]cnt+=1;print(cnt,end=' ') [tab]if sys("diff hide.out hide.ans"):break [tab]print("AC") print("WA") xzz_666 2018-01-17 21:54 9楼
想知道 AAAWAAAAAA 的是怎么改的。。。 xzz_666 2018-01-17 09:40 8楼
O(mlogmlogn)的算法强行撸过，感觉亵渎了神题…… 居然在BZOJ上卡过了……COGS上最慢点到了4s FoolMike 2017-06-03 21:20 7楼
multiset好慢。。 lyxin65 2016-01-09 23:58 6楼
回复 @cstdio : 木有，我的代码太丑了，有两个点w了。最后用了从网上找的一份代码，打算有时间再重写一遍 mikumikumi 2015-09-20 12:07 5楼
回复 @mikumikumi : %%%%% cstdio 2015-09-20 09:06 4楼
跑的快的那个是某大神写的，已换成官方数据 mikumikumi 2015-09-17 16:13 3楼
回复 @cstdio : 我在tyvj上评测的 mikumikumi 2015-09-16 23:20 2楼

2036. [ZJOI 2007]捉迷藏

★★★★ 输入文件：hide.in 输出文件：hide.out 简单对比
时间限制：10 s 内存限制：512 MiB

【题目描述】

Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。

游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。

我们将以如下形式定义每一种操作：

C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。

G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。

【输入格式】

第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如上文所示。

【输出格式】

对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出0；若所有房间的灯都开着，输出-1。

【样例输入】

【样例输出】

【提示】

对于20%的数据， N ≤50, M ≤100；

对于60%的数据， N ≤3000, M ≤10000；

对于100%的数据， N ≤100000, M ≤500000。

【来源】

http://www.tyvj.cn

曹钦翔《数据结构的提炼与压缩》