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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50, lg = (int)(log2(maxn)) + 1;
queue<int> q;
int n, m, tot, head[maxn], nxt[maxn << 1], ver[maxn << 1], edge[maxn << 1];
ll ans, d[maxn], dis[maxn], f[maxn][lg];
int cnt, dfn[maxn];
set<pair<int, int>> s;
void add(int x, int y, int z) {
ver[++tot] = y, nxt[tot] = head[x], edge[tot] = z, head[x] = tot;
}
void bfs() {
d[1] = 1, q.push(1);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (d[y]) continue;
d[y] = d[x] + 1;
q.push(y);
f[y][0] = x;
for (int j = 1; j < lg; ++j) f[y][j] = f[f[y][j - 1]][j - 1];
}
}
}
int lca(int x, int y) {
if (d[x] < d[y]) swap(x, y);
for (int i = lg - 1; i >= 0; --i) {
if (d[f[x][i]] >= d[y]) x = f[x][i];
}
if (x == y) return x;
for (int i = lg - 1; i >= 0; --i) {
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
ll dist(int x, int y) { return dis[x] + dis[y] - 2 * dis[lca(x, y)]; }
void dfs(int x, int f) {
dfn[x] = ++cnt;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (y == f) continue;
dis[y] = dis[x] + edge[i];
dfs(y, x);
}
}
int pre(int x) {
set<pair<int, int>>::iterator it = s.lower_bound(make_pair(dfn[x], x));
if (it == s.begin()) it = s.end();
return (--it)->second;
}
int suf(int x) {
set<pair<int, int>>::iterator it = s.upper_bound(make_pair(dfn[x], x));
if (it == s.end()) it = s.begin();
return it->second;
}
void insert(int x) {
if (s.size() == 0)
ans = 0;
else if (s.size() == 1)
ans += 2 * dist(s.begin()->second, x);
else {
int l = pre(x), r = suf(x);
ans += dist(l, x) + dist(x, r) - dist(l, r);
}
s.insert({dfn[x], x});
}
void erase(int x) {
s.erase({dfn[x], x});
if (s.size() <= 1)
ans = 0;
else {
int l = pre(x), r = suf(x);
ans -= dist(l, x) + dist(x, r) - dist(l, r);
}
}
int main() {
scanf("%d", &n);
int x, y, z;
for (int i = 1; i < n; ++i) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z), add(y, x, z);
}
bfs();
dfs(1, 0);
scanf("%d", &m);
char op[2];
while (m--) {
scanf("%s", op);
if (op[0] == '+') {
scanf("%d", &x);
insert(x);
} else if (op[0] == '-') {
scanf("%d", &x);
erase(x);
} else {
printf("%lld\n", ans >> 1);
}
}
return 0;
}
|
