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
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 200006
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;
int n , m , z , q , blo;
int A[MAXN];
vector<pii> G[MAXN];
set<pii> S; long long ans;
int dfn[MAXN] , clo , bac[MAXN] , dep[MAXN] , g[MAXN][19];
ll sdep[MAXN];
void dfs( int u , int fa ) {
dfn[u] = ++ clo; bac[clo] = u;
for( auto t : G[u] ) if( t.fi != fa ) {
int v = t.fi;
dep[v] = dep[u] + 1 , sdep[v] = sdep[u] + t.se;
g[v][0] = u;
for( int k = 1 ; k < 19 ; ++ k ) if( g[g[v][k-1]][k-1] )
g[v][k] = g[g[v][k-1]][k-1]; else break;
dfs( t.fi , u );
}
}
int lca( int u , int v ) {
if( dep[u] < dep[v] ) swap( u , v );
if( dep[u] != dep[v] )
for( int k = 18 ; k >= 0 ; -- k ) if( dep[g[u][k]] >= dep[v] )
u = g[u][k];
if( u == v ) return u;
for( int k = 18 ; k >= 0 ; -- k ) if( g[u][k] != g[v][k] )
u = g[u][k] , v = g[v][k];
return g[u][0];
}
ll dis( int u , int v ) {
int l = lca( u , v );
return sdep[u] + sdep[v] - 2 * sdep[l];
}
void solve() {
cin >> n;
int u , v , w;
rep( i , 1 , n - 1 ) scanf("%d%d%d",&u,&v,&w) , G[u].eb( mp( v , w ) ) , G[v].eb( mp( u , w ) );
dep[1] = 1; dfs( 1 , 1 );
char ch[4];
cin >> q;
rep( i , 1 , q ) {
scanf("%s",ch);
if( ch[0] == '-' ) {
scanf("%d",&u);
if( S.size() <= 1 ) { S.clear(); continue; }
auto nxt = S.upper_bound( mp( dfn[u] , 0x3f3f3f3f ) ) , pre = nxt;
-- pre;
auto cur = pre;
if( pre == S.begin() ) pre = S.end();
-- pre;
if( nxt == S.end() ) nxt = S.begin();
int pr = pre -> se , nx = nxt -> se;
ans -= dis( u , pr ) + dis( u , nx );
ans += dis( pr , nx );
S.erase( cur );
} else if( ch[0] == '+' ) {
scanf("%d",&u);
if( !S.size() ) { S.insert( mp( dfn[u] , u ) ); continue; }
auto nxt = S.upper_bound( mp( dfn[u] , 0x3f3f3f3f ) ) , pre = nxt;
if( nxt == S.begin() ) pre = S.end();
-- pre;
if( nxt == S.end() ) nxt = S.begin();
int pr = pre -> se , nx = nxt -> se;
ans -= dis( pr , nx );
ans += dis( pr , u ) + dis( u , nx );
S.insert( mp( dfn[u] , u ) );
} else {
printf("%lld\n",ans / 2);
}
}
}
signed main() {
solve();
}
|
