记录编号	563503	评测结果	AWWWWWWWWW
题目名称	3552.异象石	最终得分	10
用户昵称	yrtiop	是否通过	未通过
代码语言	C++	运行时间	0.743 s
提交时间	2021-08-18 12:34:34	内存使用	11.83 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using  namespace std;
const int maxn = 100005;
int ans = 0;
int n,m;
int tot;
int point[maxn];
int head[maxn],ver[maxn << 1],nxt[maxn << 1],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;
		point[pos[x]] = p;
		son[p][0] = son[p][1] = 0;
		size[p] = cnt[p] = 1;
		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(!p) {
				p = 0;
			}
		}
		else if(!son[p][0]&&son[p][1]) {
			rotate(p , 0);
			remove(son[p][0] , x);
		}
		else if(son[p][0]&&!son[p][1]) {
			rotate(p , 1);
			remove(son[p][1] , 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 -1e9;
	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 1e9;
	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],dis[maxn],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;
	}
	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];
}
int 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,int fa) {
	pos[dfn[u] = ++ tot] = u;
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i];
		if(v == fa)continue ;
		f[v][0] = u;
		d[v] = d[u] + 1;
		dis[v] = dis[u] + cost[i];
		LCApre(v , d[v]);
		dfs(v , u);
	}
	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 , 0);
	scanf("%d",&m);
	for(int i = 1;i <= m;++ i) {
		char op;
		scanf(" %c",&op);
		if(op == '+') {
			int u;
			scanf("%d",&u); 
			insert(rt , dfn[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);
		}
		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("%d\n",ans >> 1);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}