记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	int dfn,num;
	bool operator < (const node e) const{
		return dfn<e.dfn;
	}
}point;
int n,m,dfn[100005],deep[100005],fa[100005][25];
int u[100005],v[100005],cnt;
ll dis[100005],ans,w[100005];
set<node>s;
vector<int>tree[100005];
void dfs(int now,int pre);
int get_lca(int x,int y);
ll get_dis(int x,int y);
signed main(){
//	freopen("114514.in","r",stdin);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u[i]>>v[i]>>w[i];
		tree[u[i]].push_back(i);
		tree[v[i]].push_back(i);
	}
	for(int j=1;j<=log2(n);j++){
		for(int i=1;i<=n;i++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	deep[1]=1;dfn[1]=1;fa[1][0]=1;cnt=dfn[1];
	dfs(1,0);
	cin>>m;
	for(int i=1;i<=m;i++){
		char a;
		cin>>a;
		int x;
		if(a=='+'||a=='-'){
			cin>>x;
			point=node({dfn[x],x});
			if(a=='+'){
				s.insert(point);
			}
			auto pre=s.lower_bound(point);
			auto nxt=s.upper_bound(point);
			if(pre==s.begin()) pre=s.end();
			if(nxt==s.end()) nxt=s.begin();
			pre--;
			ll d=get_dis(x,(*pre).num)+get_dis(x,(*nxt).num)-get_dis((*pre).num,(*nxt).num);
			if(a=='+') ans+=d;
			else{
				ans-=d;
				s.erase(point);
			}
		}else{
			cout<<abs(ans/2)<<endl;
		}
	}
	return 0;
}
void dfs(int now,int pre){
	fa[now][0]=pre;
	for(auto i:tree[now]){
		int to=u[i];
		if(to==now) to=v[i];
		if(to!=pre){
			deep[to]=deep[now]+1;
			dfn[to]=++cnt;
			dis[to]=dis[now]+w[i];
			dfs(to,now);
		}
	}
}
int get_lca(int x,int y) {
	if(deep[x]<deep[y]) swap(x,y);
	int lg=log2(deep[x]-deep[y]);
	for(int i=lg;i>=0;i--){
		if(deep[fa[x][i]]<deep[y] || deep[fa[x][i]]==0)
			continue;
		x=fa[x][i];
	}
	if(x==y) return x;
	lg=log2(deep[y]+1);
	for(int i=lg;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
ll get_dis(int x,int y){
	int lca=get_lca(x,y);
	return dis[x]+dis[y]-2*dis[lca];
}
``