P2056 [ZJOI2007] 捉迷藏

题面：

题目描述

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

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

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

• C(hange) i 改变第 $i$ 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
• G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。

输入格式

第一行包含一个整数 $N$，表示房间的个数，房间将被编号为 $1,2,3\dots N$ 的整数。

接下来 $N-1$ 行每行两个整数 $a$, $b$，表示房间 $a$ 与房间 $b$ 之间有一条走廊相连。

接下来一行包含一个整数 $Q$，表示操作次数。接着 $Q$ 行，每行一个操作，如上文所示。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

4
3
3
4

提示

对于$20\%$的数据， $N\le 50$, $M\le 100$；

对于$60\%$的数据， $N\le 3000$, $M\le 10000$；

对于$100\%$的数据， $N\le 100000$, $M\le 500000$。

出现 & 消失！

太棒了，线段树分治！

我们建立时间线段树，将每个点的出现到消失时间插入线段树里面。

然后是结论时间！

结论：当树中新加入一个节点 $x$，原先的 $u⇝v$ 直径，只会变成 $u⇝x$ 或 $x⇝v$

证明：若插入一个 $x$，如果原直径是 $u⇝v$，而新直径是 $x⇝y$，则 $u⇝y$ 或 $v⇝y$ 肯定比 $u⇝v$ 更长，故矛盾！

那么我们要在栈中记录 $u,v$，然后通过上面的结论，更新 $u,v$，退出线段树节点时撤回退栈。

然后对每个时间点，记录答案。

求两点距离，考虑树剖 + 树上差分。

AC-code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
int rd() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;
}
void wt(int x) {static int sta[35];int f = 1;if(x < 0) f = -1,x *= f;int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);if(f == -1) putchar('-');while (top) putchar(sta[--top] + 48);
}
const int N = 5e5+5;
int head[N],nxt[N<<1],to[N<<1],cnt;
void init() {memset(head,-1,sizeof(head));cnt = 0;}
void add(int u,int v) {nxt[cnt] = head[u];to[cnt] = v;head[u] = cnt++;
}
int lst[N],n,q;
int fa[N],siz[N],top[N],son[N],dep[N];
void dfs1(int x,int f) {fa[x] = f;siz[x] = 1;dep[x] = dep[f] + 1;for(int i = head[x];~i;i = nxt[i]) {int y = to[i];if(y ^ f) {dfs1(y,x);siz[x] += siz[y];if(siz[son[x]] < siz[y]) son[x] = y;}}
}
void dfs2(int x,int topx) {top[x] = topx;if(!son[x]) return;dfs2(son[x],topx);for(int i = head[x];~i;i = nxt[i]) {int y = to[i];if(y ^ fa[x] && y ^ son[x]) dfs2(y,y);}
}
int lca(int x,int y) {while(top[x] ^ top[y]) {if(dep[top[x]] < dep[top[y]]) swap(x,y);x = fa[top[x]];}return dep[x] < dep[y] ? x : y;
}
bitset<N> col,qb;
vector<int> t[N<<2];
stack<pii> st;
int u,v,ans[N];
int dis(int x,int y) {return dep[x] + dep[y] - 2 * dep[lca(x,y)];
}
#define mid ((pl + pr) >> 1)
#define ls (p << 1)
#define rs (ls | 1)
void insert(int p,int pl,int pr,int l,int r,int x) {if(l <= pl && pr <= r) {t[p].emplace_back(x);return;}if(l <= mid) insert(ls,pl,mid,l,r,x);if(r > mid) insert(rs,mid+1,pr,l,r,x);
}
void solve(int p,int pl,int pr) {auto now = st.size();for(int x : t[p]) {st.push({u,v});if(!u && !v) u = v = x;else {int d0 = dis(u,v),d1 = dis(u,x),d2 = dis(v,x);int d = max(d0,max(d1,d2));if(d == d1) v = x;else if(d == d2) u = x;}}if(pl == pr) ans[pl] = (!u || !v) ? -1 : dis(u,v);else solve(ls,pl,mid),solve(rs,mid+1,pr);while(st.size() != now) {auto t = st.top();u = t.first,v = t.second;st.pop();}
}signed main() {init();n = rd();for(int i = 1;i<n;i++) {int u = rd(),v = rd();add(u,v);add(v,u);}q = rd();dfs1(1,0);dfs2(1,1);for(int i = 1;i<=n;i++) lst[i] = 1; for(int i = 1;i<=q;i++) {char op = getchar();while(op != 'C' && op != 'G') op = getchar();if(op == 'C') {int s = rd();if(!col[s]) {col[s] = 1;insert(1,1,q,lst[s],i,s);}else col[s] = 0,lst[s] = i;}else qb[i] = 1;}for(int i = 1;i<=n;i++) if(!col[i]) insert(1,1,q,lst[i],q,i);solve(1,1,q);for(int i = 1;i<=q;i++)if(qb[i])wt(ans[i]),putchar('\n');return 0;
}