我在学习点分治时,一直卡在这道题,今天我一鼓作气想尽办法终于把她 AC 了。

将要讲述的方法是动态点分治,有另一种链分治的方法个人感觉较为麻烦且不自然就不在此赘述。

首先静态点分治一遍建立点分树,并算出初始答案,存储每个节点作为重心时到上一个节点的边。当动态修改时从底层向上逐层修改直到抵达根节点。

对于每个节点,我们存储每个子树中距离最远的点(用 son 维护)和距离当前节点距离最远的点(用 hep 维护),最后再维护一个答案堆 ans 供查询。这个堆要资瓷添加和删除操作,可以用经典的建两个堆的方法,一个插入,一个删除即可。

其他当前子树中没有白色时应该返回 $-inf$ ,否则与当前子树的根节点是白色节点时等价的 qwq。

如上,下面上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

char readc() {
char c = getchar();
while (c != 'A' && c != 'C') c = getchar();
return c;
}

const int maxn = 100010, maxm = 200010;
const int inf = 1e9;

int n, m, u, v, k, w, cnt, a[maxn];
int core, root, from, full;
int max[maxn], siz[maxn], vis[maxn], pre[maxn], old[maxm];
std::vector < int > vec[maxn], dis[maxn];

struct Heap {
std::priority_queue < int > ins, del;
void update() {
while (ins.size() && del.size())
if (ins.top() == del.top()) {
ins.pop(), del.pop();
} else break;
}
void push(int x) { ins.push(x); }
void pop(int x) { del.push(x); update(); }
int top() { update(); return ins.size() ? ins.top() : -inf; }
int size() { return ins.size() - del.size(); }
int query() {
if (size() < 2) return 0;
int tmp1 = top();
pop(tmp1);
int tmp2 = top();
push(tmp1);
return std::max(tmp1 + tmp2, 0);
}
} ans, hep[maxn], son[maxm];

int tot = 2, hed[maxn], nxt[maxm], to[maxm], val[maxm];

void add_edge(int u, int v, int w) {
nxt[tot] = hed[u], to[tot] = v, val[tot] = w;
hed[u] = tot++;
}

void dfs(int u, int father, int udis) {
max[u] = 0, siz[u] = 1;
if (~from) {
vec[u].push_back(from);
dis[u].push_back(udis);
son[from].push(udis);
}
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (v != father && !vis[v]) {
dfs(v, u, udis + val[i]);
siz[u] += siz[v];
max[u] = std::max(max[u], siz[v]);
}
max[u] = std::max(max[u], full - siz[u]);
if (max[core] > max[u]) core = u;
}

void solve(int u, int father) {
vis[u] = true;
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (v != father && !vis[v]) {
core = 0, full = siz[v], from = i, max[core] = inf;
dfs(v, u, 0);
pre[core] = i;
solve(core, u);
hep[u].push(son[i].top() + val[i]);
old[i] = son[i].top();
}
hep[u].push(0);
ans.push(hep[u].query());
}

void insert(int u) {
ans.pop(hep[u].query());
hep[u].push(0);
ans.push(hep[u].query());
for (int i = 0; i < (int)vec[u].size(); i++)
son[vec[u][i]].push(dis[u][i]);
for (int i = pre[u]; ~i; i = pre[u]) {
u = to[i ^ 1];
if (old[i] ^ son[i].top()) {
ans.pop(hep[u].query());
hep[u].pop(old[i] + val[i]);
hep[u].push(son[i].top() + val[i]);
ans.push(hep[u].query());
old[i] = son[i].top();
}
}
}

void erase(int u) {
ans.pop(hep[u].query());
hep[u].pop(0);
ans.push(hep[u].query());
for (int i = 0; i < (int)vec[u].size(); i++)
son[vec[u][i]].pop(dis[u][i]);
for (int i = pre[u]; ~i; i = pre[u]) {
u = to[i ^ 1];
if (old[i] ^ son[i].top()) {
ans.pop(hep[u].query());
hep[u].pop(old[i] + val[i]);
hep[u].push(son[i].top() + val[i]);
ans.push(hep[u].query());
old[i] = son[i].top();
}
}
}

int main() {

n = read();
for (int i = 1; i < n; i++) {
u = read(), v = read(), w = read();
add_edge(u, v, w);
add_edge(v, u, w);
}

max[0] = inf, full = n, from = -1;
dfs(1, 0, 0);
pre[core] = -1;
solve(core, 0);

m = read();
cnt = n;
for (int i = 1; i <= m; i++) {
if (readc() == 'A') {
if (cnt) printf("%d\n", (cnt - 1) && ans.size() ? ans.top() : 0);
else printf("They have disappeared.\n");
} else {
k = read();
if (a[k]) {
cnt++, a[k] = 0;
insert(k);
} else {
cnt--, a[k] = 1;
erase(k);
}
}
}

return 0;
}