记录编号	563522	评测结果	AAAAAAAAAA
题目名称	异象石	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.740 s
提交时间	2021-08-19 12:05:50	内存使用	12.63 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using  namespace std;
const int maxn = 100005;
const int INF = 1e9;
typedef long long ll;
ll ans = 0;
int n,m;
int tot;
int point[maxn];
int head[maxn],ver[maxn << 1],nxt[maxn << 1];
ll cost[maxn << 1];
void add(int u,int v,int t) {
	ver[++ tot] = v;
	nxt[tot] = head[u];
	cost[tot] = t;
	head[u] = tot;
	return ;
}
int rt,sz;
int son[maxn][2],size[maxn],key[maxn],rd[maxn],cnt[maxn];
int pos[maxn];
void pushup(int x) {
    size[x] = size[son[x][0]] + size[son[x][1]] + cnt[x];
    return ;
}
void rotate(int &x,int d) {
    int k = son[x][d ^ 1];
    son[x][d ^ 1] = son[k][d];
    son[k][d] = x;
    pushup(x);
    pushup(k);
    x = k;
    return ;
}
void insert(int &p,int x) {
    if(!p) {
        p = ++ sz;
        size[p] = cnt[p] = 1;
        son[p][0] = son[p][1] = 0;
        key[p] = x;
        rd[p] = rand();
        return ;
    }
    if(key[p] == x) {
        ++ cnt[p];
        ++ size[p];
        return ;
    }
    int d = x > key[p];
    insert(son[p][d] , x);
    if(rd[p] < rd[son[p][d]]) {
        rotate(p , d ^ 1);
    }
    pushup(p);
    return ;
}
void remove(int &p,int x) {
    if(!p)return ;
    if(key[p] != x) {
        remove(son[p][x > key[p]] , x);
    }
    else {
        if(!son[p][0]&&!son[p][1]) {
            -- cnt[p];
            -- size[p];
            if(!cnt[p]) {
                p = 0;
            }
        }
        else if(son[p][0]&&!son[p][1]) {
            rotate(p , 1);
            remove(son[p][1] , x);
        }
        else if(!son[p][0]&&son[p][1]) {
            rotate(p , 0);
            remove(son[p][0] , x);
        }
        else {
            int d = rd[son[p][0]] > rd[son[p][1]];
            rotate(p , d);
            remove(son[p][d] , x);
        }
    }
    pushup(p);
    return ;
}
int pre(int p,int x) {
    if(!p)return -INF;
    if(key[p] >= x)return pre(son[p][0] , x);
    else return max(key[p] , pre(son[p][1] , x));
}
int suff(int p,int x) {
    if(!p)return INF;          
    if(key[p] <= x)return suff(son[p][1] , x);
    else return min(key[p] , suff(son[p][0] , x));
}
int Minimum(int p) {
	if(!son[p][0])return key[p];
	return Minimum(son[p][0]);
}
int Maximum(int p) {
	if(!son[p][1])return key[p];
	return Maximum(son[p][1]);
}
int lg[maxn],f[maxn][20];
int d[maxn];
ll dis[maxn];
int dfn[maxn];
int LCA(int u,int v) {
	if(d[u] < d[v])swap(u , v);
	for(int k = lg[d[u]];~ k;-- k) {
		if(d[u] - (1 << k) >= d[v]) {
			u = f[u][k];
		}
		if(u == v)return u;
	}
	if(u == v)return u;
	for(int k = lg[d[u]];~ k;-- k) {
		if(f[u][k] != f[v][k]) {
			u = f[u][k];
			v = f[v][k];
		}
	}
	return f[u][0];
}
ll dist(int u,int v) {
	return dis[u] + dis[v] - (dis[LCA(u , v)] << 1);
}
void LCApre(int u,int d) {
	for(int k = 1;k <= lg[d];++ k)f[u][k] = f[f[u][k - 1]][k - 1];
	return ;
}
void dfs(int u) {
	pos[dfn[u] = ++ tot] = u;
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i];
		if(dfn[v])continue ;
		f[v][0] = u;
		d[v] = d[u] + 1;
		dis[v] = dis[u] + cost[i];
		LCApre(v , d[v]);
		dfs(v);
	}
	return ;
}                      
int main() {
	freopen("visionstone.in","r",stdin);
	freopen("visionstone.out","w",stdout);
	scanf("%d",&n);
	for(int i = 2;i <= n;++ i) {
		int u,v,t;
		scanf("%d%d%d",&u,&v,&t);
		add(u , v , t);
		add(v , u , t);
		lg[i] = lg[i >> 1] + 1;
	}
	tot = 0;
	dfs(1);
	scanf("%d",&m);
	for(int i = 1;i <= m;++ i) {
		char op;
		scanf(" %c",&op);          
		if(op == '+') {
			int u;
			scanf("%d",&u); 
			if(sz) {
				int x1 = pre(rt , dfn[u]),x2 = suff(rt , dfn[u]);
				if(x1 == -1e9)x1 = Maximum(rt);
				if(x2 == 1e9)x2 = Minimum(rt);
				int p = pos[x1],s = pos[x2];
				ans -= dist(p , s);               
				ans += dist(p , u) + dist(u , s);
			}
			insert(rt , dfn[u]);
		}                  
		else if(op == '-') {                               
			int u;      
			scanf("%d",&u);        
			int x1 = pre(rt , dfn[u]),x2 = suff(rt , dfn[u]);
			if(x1 == -1e9)x1 = Maximum(rt);
			if(x2 == 1e9)x2 = Minimum(rt);
			int p = pos[x1],s = pos[x2];
			ans += dist(p , s);
			ans -= dist(p , u) + dist(u , s);
			remove(rt , dfn[u]);       
		}
		else {
			printf("%lld\n",ans >> 1);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}