【bzoj1095】[ZJOI2007]Hide 捉迷藏

2015年4月20日7,5047

Description

捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: C(hange) i 改变第i个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的距离。

Input

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

Output

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

Sample Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

Sample Output

4
3
3
4

HINT

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

题解

2014.11.28
括号序列神题。。。
大家一起膜拜岛娘吧
。。。
2015.4.20
其实。。。我至今没有完全掌握括号序列的做法。。。
在PoPoQQQ大爷和KuribohG的指导下我学会了奇怪的分治做法
大爷称之动态树分治。。。
一开始写的可并堆感觉自己快炸了…
其实这种做法不难。。。就是代码长。。。
把每次分治的重心连成一棵树,树的深度是logn,每次修改一个结点只影响它到树根的一条链
这题具体实现的时候要维护三层堆
C.每个重心存所有子树到其距离
B.每个重心存各个子树最大值,即子结点堆C的最大值
A.全局一个堆,维护答案最大值,存每个堆B的最大值和次大值之和
树上距离用rmq来求比较优越2333
线段树

分治