[Codeforces176E] Archaeology

做法

随便取一个点作根,用线段树按 dfs 序维护存在的点,维护一下所有存在的点的 lca 和到根的路径的并的长度即可。

误以为要减去点数 * lca 的深度,调了好久...

一直调不出来可能需要检查一下是不是哪里想错了。

代码

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

using namespace std;

const int maxn = 100010;
typedef long long ll;

char opt[10];

ll dis[maxn];

int n, l[maxn], fa[maxn][20], e, q;
int dfn[maxn], dep[maxn], tim;

struct Edge {
int v, w, x;
} E[maxn<<1];

void dfs(int u, int f) {
dfn[u] = ++ tim;
fa[u][0] = f;
for (int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i-1]][i-1];
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f) {
dis[v] = dis[u] + E[p].w;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
}

int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
if (dep[u] > dep[v]) {
int c = dep[u] - dep[v];
for (int i = 0; i < 20; i++) {
if (c & (1<<i)) {
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];
}

struct dat {
int s, t, l;
ll sum;
} T[maxn<<2];

inline void addEdge(int u, int v, int w) {
E[e].v = v, E[e].x = l[u], E[e].w = w, l[u] = e++;
}

dat operator+(const dat &d1, const dat &d2) {
if (!d1.l) return d2;
if (!d2.l) return d1;
dat ret;
ret.s = d1.s, ret.t = d2.t;
ret.l = lca(d1.l, d2.l);
ret.sum = d1.sum + d2.sum - dis[lca(d1.t, d2.s)];
return ret;
}

void pushUp(int rt) {
T[rt] = T[rt<<1] + T[rt<<1|1];
}

void upd(int p, int v, int l, int r, int rt) {
if (l == r) {
T[rt].l = T[rt].s = T[rt].t = v;
T[rt].sum = dis[v];
return;
}
int m = (l + r) >> 1;
if (p <= m) upd(p, v, l, m, rt<<1);
else upd(p, v, m+1, r, rt<<1|1);
pushUp(rt);
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w), addEdge(v, u, w);
}
dfs(1, 0);
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
scanf("%s", opt);
if (opt[0] == '+') {
int x; scanf("%d", &x);
upd(dfn[x], x, 1, n, 1);
} else if (opt[0] == '-') {
int x; scanf("%d", &x);
upd(dfn[x], 0, 1, n, 1);
} else {
printf("%lld\n", T[1].sum - dis[T[1].l]);
}
}
return 0;
}