ZJOI2007捉迷藏：动态点分治的应用

### 题目背景
Jiajia 和 Wind 是一对幸福的家庭，他们育有多名子女。某天，全家决定利用家中独特的建筑布局——由 N 个房间和 N-1 条双向走廊组成的空间，进行一场别开生面的捉迷藏游戏。每个房间均可通过走廊与其他房间连通。

### 游戏规则
- 孩子们选择未开灯的房间藏匿。
- Wind 可以根据孩子们的要求随意开关灯光，增加游戏的趣味性和挑战性。
- Jiajia 的任务是在每次游戏开始时，计算出最远的两个未开灯房间之间的距离，以此评估游戏的难度。

### 输入输出格式
- **输入**：首先输入一个整数 N 表示房间数量，随后 N-1 行描述每条走廊连接的两个房间。最后一行输入一个整数 Q 表示操作次数，之后 Q 行分别给出具体的操作指令，包括改变房间的照明状态（C i）或开始一次游戏（G）。
- **输出**：对于每个 G 操作，输出一行非负整数表示最远的两个未开灯房间的距离。如果只有一个房间的灯是关着的，输出 0；如果所有房间的灯都是开着的，输出 -1。

### 解题思路
此问题可通过构建括号序列的方法解决。通过深度优先搜索（DFS），在访问每个节点时加入左括号，在回溯时加入右括号，从而形成一个代表树结构的括号序列。利用这一序列，可以方便地计算任意两点间的距离。

### 算法实现
1. **括号序列的构建**：使用 DFS 遍历树，记录每个节点的进入和离开时间，形成括号序列。
2. **距离计算**：通过分析括号序列中特定子序列的括号数量，计算两点间的距离。
3. **数据结构的选择**：采用线段树来高效地处理区间更新和查询操作，确保算法的时间复杂度满足题目要求。

### 代码实现
```cpp
#include
#define lc (hao<<1)
#define rc (hao<<1|1)
#define inf 214748364
#define N 100010
using namespace std;

struct Data {
int a, b, l1, l2, r1, r2, sum;
} tree[N<<4];

int to[N<<1], nxt[N<<1], head[N], st[N<<2], nct, cnt, tot, val[N], n, m, x, y;
bool is[N];
char op[2];

void addEdge(int x, int y) {
to[++nct] = y;
nxt[nct] = head[x];
head[x] = nct;
}

void dfs(int u, int fa) {
st[++cnt] = -1;
st[++cnt] = u;
val[u] = cnt;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v != fa) dfs(v, u);
}
st[++cnt] = -2;
}

void updateNode(int hao) {
if (tree[lc].b > tree[rc].a) {
tree[hao].a = tree[lc].a;
tree[hao].b = tree[lc].b - tree[rc].a + tree[rc].b;
} else {
tree[hao].b = tree[rc].b;
tree[hao].a = tree[rc].a - tree[lc].b + tree[lc].a;
}
tree[hao].l1 = max(tree[lc].l1, max(tree[rc].l1 + tree[lc].a - tree[lc].b, tree[rc].l2 + tree[lc].a + tree[lc].b));
tree[hao].l2 = max(tree[lc].l2, tree[rc].l2 - tree[lc].a + tree[lc].b);
tree[hao].r1 = max(tree[rc].r1, max(tree[lc].r1 - tree[rc].a + tree[rc].b, tree[lc].r2 + tree[rc].a + tree[rc].b));
tree[hao].r2 = max(tree[rc].r2, tree[lc].r2 + tree[rc].a - tree[rc].b);
tree[hao].sum = max(max(tree[lc].sum, tree[rc].sum), max(tree[lc].r1 + tree[rc].l2, tree[lc].r2 + tree[rc].l1));
}

void change(int hao, int x) {
tree[hao].a = tree[hao].b = 0;
tree[hao].l1 = tree[hao].r1 = tree[hao].l2 = tree[hao].r2 = tree[hao].sum = -inf;
if (st[x] == -1) tree[hao].b = 1;
else if (st[x] == -2) tree[hao].a = 1;
else if (!is[st[x]]) {
tree[hao].l1 = tree[hao].r1 = tree[hao].l2 = tree[hao].r2 = 0;
}
}

void buildTree(int hao, int l, int r) {
if (l == r) {
change(hao, l);
return;
}
int mid = (l + r) >> 1;
buildTree(lc, l, mid);
buildTree(rc, mid + 1, r);
updateNode(hao);
}

void updateTree(int hao, int l, int r, int x) {
if (l == r) {
change(hao, l);
return;
}
int mid = (l + r) >> 1;
if (x <= mid) updateTree(lc, l, mid, x);
else updateTree(rc, mid + 1, r, x);
updateNode(hao);
}

int main() {
scanf("%d", &n);
for (int i = 1; i scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}
dfs(1, -1);
tot = n;
buildTree(1, 1, cnt);
scanf("%d", &m);
while (m--) {
scanf("%s", op);
if (op[0] == 'G') {
if (tot == 1) puts("0");
else if (tot == 0) puts("-1");
else printf("%d\n", tree[1].sum);
} else {
scanf("%d", &x);
if (is[x]) {
tot++;
is[x] = 0;
} else {
tot--;
is[x] = 1;
}
updateTree(1, 1, cnt, val[x]);
}
}
return 0;
}
```
### 总结
通过构建括号序列并结合线段树的数据结构，本题提供了一个高效解决动态点分治问题的方法。这种方法不仅能够快速响应各种操作，还能准确计算出游戏中最远的两个未开灯房间的距离，为玩家提供了丰富的游戏体验。