[ZJOI2007]Hide 捉迷藏

Time Limit:40000MS  Memory Limit:165536K
Total Submit:121 Accepted:48
Case Time Limit:5000MS

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

对于20%的数据， N ≤50, M ≤100；
对于60%的数据， N ≤3000, M ≤10000；
对于100%的数据， N ≤100000, M ≤500000。

Source

这个题目CQX的题解是用线段树加上括号序列的性质。。但我觉得太繁琐了。。
还是树链剖分的树的分治好理解。。但是好理解归好理解。。一看就知道要写N行囧。。
本着锻炼代码能力，歌颂伟大领袖毛主席的想法。。我还是去写了。。
写了半天。。居然1A了囧。。。。
其实基于链的树的分治就是把树
…………..
….   ….
….
的形状。。。
然后每条路径就是它所在的最高链中一段，加上通下去的两条。。。
Code在网盘上囧。。。