这题真是十分难写啊 不管是点分治还是括号序列都有一堆细节。。
点分治：时空复杂度$O(n\log^2n)$，常数巨大
主要就是3个堆的初始状态
C堆：每个节点一个，为子树中的点到它父亲的距离的堆。
B堆：每个节点一个，存所有儿子的堆的堆顶。特别地，如果该节点关灯，那么将加入一个0；如果没有元素，堆顶应返回负数。
A堆：全局一个，存所有B堆的最大值和最小值之和。特别地，如果B堆不足两个，返回负数。
这样，我们一开始需要关闭所有的等，即对所有点调用一次turn_off。由于堆顶返回的是负数，删除时找不到的话直接忽略即可，如果返回的是0，则有可能误删有用的信息。
代码：
![bzoj1095: [ZJOI2007]Hide 捉迷藏 线段树维护括号序列 点分治 链分治](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0hNNkx5OXBiV0ZuWlhNdVkyNWliRzluY3k1amIyMHZUM1YwYkdsdWFXNW5TVzVrYVdOaGRHOXljeTlEYjI1MGNtRmpkR1ZrUW14dlkyc3VaMmxt.jpg?w=700&webp=1 "bzoj1095: [ZJOI2007]Hide 捉迷藏 线段树维护括号序列 点分治 链分治")
![bzoj1095: [ZJOI2007]Hide 捉迷藏 线段树维护括号序列 点分治 链分治](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0hNNkx5OXBiV0ZuWlhNdVkyNWliRzluY3k1amIyMHZUM1YwYkdsdWFXNW5TVzVrYVdOaGRHOXljeTlGZUhCaGJtUmxaRUpzYjJOclUzUmhjblF1WjJsbQ%3D%3D.jpg?w=700&webp=1 "bzoj1095: [ZJOI2007]Hide 捉迷藏 线段树维护括号序列 点分治 链分治")
1 #include<bits/stdc++.h>点分治
2
3 using namespace std;
4
5 const int N = 100000 + 10, logn = 17;
6
7 struct RMQ {
8 int n, f[logn + 1][N * 2], Log[N * 2];
9 void init(int n) {
10 Log[0] = -1;
11 for(int i = 1; i <= n; i++) Log[i] = Log[i >> 1] + 1;
12 this->n = n;
13 for(int i = 1; (1 << i) < n; i++) {
14 for(int j = 1; j <= n; j++) {
15 f[i][j] = min(f[i-1][j], f[i-1][j + (1 << (i-1))]);
16 }
17 }
18 }
19
20 int query(int l, int r) {
21 int t = Log[r - l + 1];
22 return min(f[t][l], f[t][r - (1 << t) + 1]);
23 }
24 } rmq;
25
26 struct Edge {
27 int to; Edge *next;
28 } pool[N * 2], *pis = pool, *fir[N];
29
30 void AddEdge(int u, int v) {
31 pis->to = v, pis->next = fir[u], fir[u] = pis++;
32 }
33
34 int dfn[N], dfs_clock, *seq = rmq.f[0], dep[N], ds[N], tot;
35
36 #define v p->to
37 void dfs(int u, int fa) {
38 dfn[u] = ++dfs_clock;
39 seq[dfs_clock] = dep[u];
40 for(Edge *p = fir[u]; p; p = p->next) {
41 if(v != fa) {
42 dep[v] = dep[u] + 1, dfs(v, u);
43 seq[++dfs_clock] = dep[u];
44 }
45 }
46 ds[tot++] = u;
47 }
48 #undef v
49
50 int dis(int u, int v) {
51 if(dfn[u] > dfn[v]) swap(u, v);
52 return dep[u] + dep[v] - (rmq.query(dfn[u], dfn[v]) << 1);
53 }
54 const int INF = 1 << 29;
55
56 struct Set {
57 multiset<int> s;
58 void insert(int x) {s.insert(x);}
59 void erase(int x) {
60 multiset<int>::iterator it = s.find(x);
61 if(it != s.end()) s.erase(it);
62 }
63 int size() const {return s.size();}
64 int top() {return s.empty() ? -INF : *--s.end();}
65 int query() {
66 if(s.size() < 2) return -INF;
67 return *--s.end() + *----s.end();
68 }
69 } A, B[N], C[N];
70
71 void print(const Set &ss) {
72 const multiset<int> &s = ss.s;
73 for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
74 printf("%d ", *it);
75 }
76 puts("");
77 }
78 bool centre[N];
79 int fa[N], maxsz[N], sz[N], root;
80
81 #define v p->to
82 void dfs_size(int u, int fa) {
83 sz[u] = 1, maxsz[u] = 0;
84 for(Edge *p = fir[u]; p; p = p->next) {
85 if(!centre[v] && v != fa) {
86 dfs_size(v, u);
87 sz[u] += sz[v];
88 maxsz[u] = max(maxsz[u], sz[v]);
89 }
90 }
91 }
92
93 void dfs_root(int u, int fa, int r) {
94 maxsz[u] = max(maxsz[u], sz[r] - sz[u]);
95 if(maxsz[u] < maxsz[root]) root = u;
96 for(Edge *p = fir[u]; p; p = p->next) {
97 if(!centre[v] && v != fa) dfs_root(v, u, r);
98 }
99 }
100
101 void divide(int u, int _fa) {
102 dfs_size(u, 0), dfs_root(u, 0, root = u);
103 centre[u = root] = 1, fa[u] = _fa;
104 for(Edge *p = fir[u]; p; p = p->next) {
105 if(!centre[v]) divide(v, u);
106 }
107 }
108 #undef v
109
110 void add(int u, int v, int flag) {
111 if(u == v) {
112 A.erase(B[u].query());
113 if(flag) B[u].insert(0);
114 else B[u].erase(0);
115 A.insert(B[u].query());
116 }
117 int f = fa[u];
118 if(!f) return;
119 A.erase(B[f].query());
120 B[f].erase(C[u].top());
121 if(flag) C[u].insert(dis(f, v));
122 else C[u].erase(dis(f, v));
123 B[f].insert(C[u].top());
124 A.insert(B[f].query());
125 add(f, v, flag);
126 }
127
128 int col[N];
129
130 int main() {
131 #ifdef DEBUG
132 freopen("in.txt", "r", stdin);
133 #endif
134
135 int n; scanf("%d", &n);
136 for(int i = 1; i < n; i++) {
137 int u, v; scanf("%d%d", &u, &v);
138 AddEdge(u, v), AddEdge(v, u);
139 }
140 dfs(1, 0);
141 rmq.init((n << 1) - 1);
142 divide(1, 0);
143 int cnt_off = n;
144 for(int i = 0; i < n; i++)
145 add(ds[i], ds[i], col[ds[i]] = 1);
146
147 int m, u; scanf("%d", &m);
148 char opt[8];
149 while(m--) {
150 scanf("%s", opt);
151 if(opt[0] == 'G') {
152 if(cnt_off == 0) puts("-1");
153 else if(cnt_off == 1) puts("0");
154 else printf("%d\n", A.top());
155 } else {
156 scanf("%d", &u), add(u, u, col[u] ^= 1);
157 if(col[u]) cnt_off++; else cnt_off--;
158 }
159 }
160
161 return 0;
162 }
括号序列：时间复杂度$O(n\log n)$,空间复杂度$O(n)$
1 #include<bits/stdc++.h>线段树 链分治：时间复杂度$O(n\log^2n)$,空间复杂度$O(n)$ 比点分治快多啦 notice：合并两个线段树节点的时候如果使用=赋值可能丢失儿子信息。
2
3 using namespace std;
4
5 const int N = 100000 + 10;
6
7 int col[N];
8 const int bracket[] = {-2, -1};
9
10 struct Data {
11 /*
12 0 : 从区间左起的
13 [ x ] x的数量
14
15 c[] 是左右括号的数量，而d[]和s[]必须保证旁边至少有一个满足条件的点
16 */
17 int c[2]; // [ )...) ] 或 [ (...( ]
18 int d[2]; // [ )...) ] - [ (...( ] 或反过来
19 int s[2]; // [ )...) ] + [ (...( ] 或反过来
20 int ans;
21
22 void set(int x) {
23 for(int i = 0; i < 2; i++) {
24 c[i] = x == bracket[i];
25 d[i] = s[i] = x > 0 && col[x] ? 0 : -(1 << 29);
26 // 只有在x是满足条件的点的时候才把d[]和s[]赋为0，否则为-INF
27 }
28 }
29 };
30
31 void maxit(int &x, int y) {
32 if(x < y) x = y;
33 }
34
35 // 实际上需要讨论lhs.c[1] 和 rhs.c[0]的大小
36 // 但是不合法的一定不是最优的，所以可以对两种情况直接取max
37 Data operator + (const Data &lhs, const Data &rhs) {
38 static Data res;
39
40 // update ans
41 res.ans = max(lhs.ans, rhs.ans);
42 maxit(res.ans, lhs.s[1] + rhs.d[0]);
43 maxit(res.ans, lhs.d[1] + rhs.s[0]);
44
45 // update s[]
46 res.s[0] = max(lhs.s[0], rhs.s[0] - lhs.c[1] + lhs.c[0]); // lhs.c[1] >= rhs.c[0]
47 res.s[0] = max(res.s[0], lhs.c[0] + lhs.c[1] + rhs.d[0]); // lhs.c[1] <= rhs.c[0]
48 res.s[1] = max(rhs.s[1], lhs.s[1] - rhs.c[0] + rhs.c[1]); // rhs.c[1] >= lhs.c[0]
49 res.s[1] = max(res.s[1], rhs.c[0] + rhs.c[1] + lhs.d[1]); // rhs.c[1] <= rhs.c[0]
50
51 // update d[]
52 res.d[0] = max(lhs.d[0], rhs.d[0] + lhs.c[1] - lhs.c[0]);
53 res.d[1] = max(rhs.d[1], lhs.d[1] + rhs.c[0] - rhs.c[1]);
54
55 // update c[] to update next s[] and d[]
56 res.c[0] = lhs.c[0] + max(rhs.c[0] - lhs.c[1], 0);
57 res.c[1] = rhs.c[1] + max(lhs.c[1] - rhs.c[0], 0);
58
59 return res;
60 }
61
62 struct Edge {int to; Edge *next;} pool[N * 2], *pis = pool, *fir[N];
63 void AddEdge(int u, int v) {pis->to = v, pis->next = fir[u], fir[u] = pis++;}
64
65 int dfs_seq[N * 3], dfs_clock;
66
67 void dfs(int u, int fa) {
68 col[u] = 1;
69 dfs_seq[++dfs_clock] = bracket[1];
70 dfs_seq[++dfs_clock] = u;
71 for(Edge *p = fir[u]; p; p = p->next) {
72 int v = p->to;
73 if(v != fa) dfs(v, u);
74 }
75 dfs_seq[++dfs_clock] = bracket[0];
76 }
77
78 int pos[N];
79
80 struct SegmentTree {
81 Data da[N * 12];
82 void build(int s, int l, int r, int a[]) {
83 if(l == r) {
84 if(a[l] > 0) pos[a[l]] = s;
85 return da[s].set(a[l]);
86 }
87 int mid = (l + r) >> 1;
88 build(s << 1, l, mid, a), build(s << 1 | 1, mid + 1, r, a);
89 da[s] = da[s << 1] + da[s << 1 | 1];
90 }
91
92 void modify(int x) {
93 int s = pos[x]; da[s].set(x);
94 while(s >>= 1) da[s] = da[s << 1] + da[s << 1 | 1];
95 }
96 } seg;
97
98 int main() {
99 #ifdef DEBUG
100 freopen("in.txt", "r", stdin);
101 #endif
102
103 int n; scanf("%d", &n);
104 for(int i = 1; i < n; i++) {
105 int u, v; scanf("%d%d", &u, &v);
106 AddEdge(u, v), AddEdge(v, u);
107 }
108 dfs(1, 0);
109 seg.build(1, 1, n * 3, dfs_seq);
110
111 int m; scanf("%d", &m);
112 char opt[8]; int ans, x, cnt = n;
113 while(m--) {
114 scanf("%s", opt);
115 if(opt[0] == 'G') {
116 if(cnt >= 2) ans = seg.da[1].ans;
117 else if(cnt == 1) ans = 0;
118 else ans = -1;
119 printf("%d\n", ans);
120 } else {
121 scanf("%d", &x);
122 if(col[x] ^= 1) cnt++; else cnt--;
123 seg.modify(x);
124 }
125 }
126
127 return 0;
128 }
1 #include<bits/stdc++.h>链分治
2
3 using namespace std;
4
5 const int N = 100000 + 10, INF = 1 << 29;
6
7 struct Set {
8 multiset<int> s;
9 void erase(int x) {assert(s.find(x) != s.end()), s.erase(s.find(x));}
10 void insert(int x) {s.insert(x);}
11 int top() const {return s.empty() ? -INF : *--s.end();}
12 int query() const {
13 if(s.size() < 2) return -INF;
14 return *--s.end() + *----s.end();
15 }
16 } heap[N], st;
17
18 void print(const Set &ss) {
19 const multiset<int> &s = ss.s;
20 for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
21 printf("%d ", *it);
22 }
23 puts("");
24 }
25
26 struct Edge {
27 int to, w;
28 Edge *next;
29 } pool_edges[N * 2], *fir[N], *pe = pool_edges;
30
31 void AddEdge(int u, int v, int w) {
32 pe->to = v, pe->w = w, pe->next = fir[u], fir[u] = pe++;
33 }
34
35 int sz[N], top[N], dis[N], son[N], fa[N], dfs_clock, seq[N], dfn[N], end[N], col[N];
36
37 #define mid ((l + r) >> 1)
38 struct Node {
39 int L, R, ans;
40 Node *ch[2];
41
42 void set(int u) {
43 ans = heap[u].query();
44 L = R = heap[u].top();
45 }
46
47 void modify(int l, int r, int p);
48
49 } pool_nodes[N * 3], *pn = pool_nodes, *rt[N];
50
51 void print(Node *o, int l, int r) {
52 printf("[%d, %d] : L = %d, R = %d, ans = %d\n", l, r, o->L, o->R, o->ans);
53 if(l != r) print(o->ch[0], l, mid), print(o->ch[1], mid + 1, r);
54 }
55 void merge(Node &res, const Node &lhs, const Node &rhs, int l, int r) {
56 res.ans = max(lhs.ans, rhs.ans);
57 res.ans = max(res.ans, lhs.R + dis[seq[mid + 1]] - dis[seq[mid]] + rhs.L);
58
59 res.L = max(lhs.L, dis[seq[mid + 1]] - dis[seq[l]] + rhs.L);
60 res.R = max(rhs.R, dis[seq[r]] - dis[seq[mid]] + lhs.R);
61 }
62
63 void Node::modify(int l, int r, int p) {
64 if(l == r) return set(seq[p]);
65 if(p <= mid) ch[0]->modify(l, mid, p);
66 else ch[1]->modify(mid + 1, r, p);
67 merge(*this, *ch[0], *ch[1], l, r);
68 }
69
70 Node *build(int l, int r) {
71 Node *o = pn++;
72 if(l == r) o->set(seq[l]);
73 else {
74 o->ch[0] = build(l, mid);
75 o->ch[1] = build(mid + 1, r);
76 merge(*o, *o->ch[0], *o->ch[1], l, r);
77 }
78 return o;
79 }
80 #undef mid
81
82 #define v it->to
83 void dfs_size(int u) {
84 sz[u] = 1, col[u] = 1;
85 for(Edge *it = fir[u]; it; it = it->next) {
86 if(v != fa[u]) {
87 dis[v] = dis[u] + it->w;
88 fa[v] = u;
89 dfs_size(v);
90 sz[u] += sz[v];
91 if(sz[v] > sz[son[u]]) son[u] = v;
92 }
93 }
94 }
95
96 void dfs_build(int u, int pre) {
97 seq[dfn[u] = ++dfs_clock] = u;
98 top[u] = pre;
99 end[pre] = max(end[pre], dfn[u]);
100 if(son[u]) dfs_build(son[u], pre);
101 for(Edge *it = fir[u]; it; it = it->next) {
102 if(v != fa[u] && v != son[u]) {
103 dfs_build(v, v);
104 heap[u].insert(rt[v]->L + dis[v] - dis[u]);
105 }
106 }
107
108 heap[u].insert(0);
109 if(top[u] == u) {
110 rt[u] = build(dfn[u], end[u]);
111 st.insert(rt[u]->ans);
112 }
113 }
114 #undef v
115
116 void modify(int u) {
117 static int anc[20], tot;
118 tot = 0;
119 for(int t = u; t; t = fa[top[t]]) anc[tot++] = t;
120
121 for(int i = tot-1; i >= 0; i--) {
122 st.erase(rt[top[anc[i]]]->ans);
123 if(i) heap[anc[i]].erase(rt[top[anc[i-1]]]->L + dis[top[anc[i-1]]] - dis[anc[i]]);
124 }
125 if(col[u]) heap[u].insert(0);
126 else heap[u].erase(0);
127
128 for(int i = 0; i < tot; i++) {
129 int x = anc[i], t = top[x];
130 rt[t]->modify(dfn[t], end[t], dfn[x]);
131 st.insert(rt[t]->ans);
132 if(i+1 < tot) heap[anc[i+1]].insert(rt[t]->L + dis[t] - dis[anc[i+1]]);
133 }
134 }
135
136 int main() {
137 #ifdef DEBUG
138 freopen("in.txt", "r", stdin);
139 #endif
140 int n; scanf("%d", &n);
141 for(int i = 1; i < n; i++) {
142 int u, v; scanf("%d%d", &u, &v);
143 AddEdge(u, v, 1), AddEdge(v, u, 1);
144 }
145 dfs_size(1);
146 dfs_build(1, 1);
147
148 int m; scanf("%d", &m);
149 char opt[8]; int u, tot = n;
150 while(m--) {
151 scanf("%s", opt);
152 if(opt[0] == 'G') {
153 int ans;
154 if(tot == 0) ans = -1;
155 else if(tot == 1) ans = 0;
156 else ans = st.top();
157 printf("%d\n", ans);
158 } else {
159 scanf("%d", &u);
160 if(!(col[u] ^= 1)) tot--; else tot++;
161 modify(u);
162
163 }
164 }
165 }