「Codeforces 176E」Archaeology【DFS 序 + 平衡树】

Description

有一棵 nn 个点的带权树,每个点都是黑色或白色,最初所有点都是白色的。有 qq 个操作:

  • 把一个点反色。
  • 查询黑点的导出子树 ((用最少的边把所有的黑点连通起来的树)) 的总边权和。

Input

第一行包含一个整数 nn (n105)(n \leqslant 10^5),表示点数。

接下来 n1n - 1 每行包含三个正整数 a,b,ca, b, c (c109)(c \leqslant 10^9),表示 aabb 间有一条权值为 cc 的边。

接下来一行包含一个整数 qq (q105)(q \leqslant 10^5),表示操作的数量。

接下来 qq 行,每行描述一个操作,有如下三种类型:

  • + x:+\ x: xx 从白点变成黑点。
  •  x:-\ x: xx 从黑点变成白点。
  • ?:?: 询问当前黑点的导出子树的总边权和。

Output

对于每个 ?? 操作,输出一个整数表示答案。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
6
1 2 1
1 3 5
4 1 7
4 5 3
6 4 2
10
+ 3
+ 1
?
+ 6
?
+ 5
?
- 6
- 3
?

Sample Output

1
2
3
4
5
14
17
10

Solution

将当前的 kk 个黑点按照 DFS\text{DFS} 序排序,设其为 v1,v2,,vkv_1, v_2, \cdots, v_k。那么边权和为:

d(v1,v2)+d(v2,v3)++d(vk1,vk)+d(vk,v1)2\frac{d(v_1, v_2) + d(v_2, v_3) + \cdots + d(v_{k - 1}, v_k) + d(v_k, v_1)}{2}

其中 d(u,v)d(u, v) 表示 uuvv。用 set 或平衡树来维护当前黑点的 DFS\text{DFS} 序即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 100010;
int n, q, dfn, pos[maxn], tid[maxn], fa[maxn][20], dep[maxn];
ll ans, g[maxn]; char op; set<int> S;
struct edge { int to, cost; };
vector<edge> G[maxn];

void dfs(int v, int f, int d) {
dep[v] = d, fa[v][0] = f, pos[tid[v] = ++dfn] = v;
for (int i = 1; (1 << i) <= dep[v]; i++) {
fa[v][i] = fa[fa[v][i - 1]][i - 1];
}
for (int i = 0; i < G[v].size(); i++) {
edge u = G[v][i]; if (u.to == f) continue;
g[u.to] = g[v] + u.cost, dfs(u.to, v, d + 1);
}
}

int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (dep[fa[u][i]] >= dep[v]) {
u = fa[u][i];
}
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i], v = fa[v][i];
}
}
return fa[u][0];
}

int main() {
scanf("%d", &n);
for (int i = 1, u, v, w; i < n; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u].push_back((edge){v, w}), G[v].push_back((edge){u, w});
}
dfs(1, 0, 1), scanf("%d", &q);
for (int i = 1, v; i <= q; i++) {
scanf("\n%c", &op);
if (op == '?') {
printf("%lld\n", ans);
} else {
scanf("%d", &v);
auto it = S.insert(tid[v]).first, L = it, R = it;
if (L-- == S.begin()) L = --S.end();
if (++R == S.end()) R = S.begin();
ll l = g[v] + g[lca(pos[*L], pos[*R])] - g[lca(v, pos[*L])] - g[lca(v, pos[*R])];
if (op == '+') ans += l;
else ans -= l, S.erase(tid[v]);
}
}
return 0;
}