题目详见蓝皮书【算法竞赛：进阶指南】。
题目大意：
就是给你一颗树，然后我们要在上面进行三种操作：
1.标记某个点 或者 2.撤销某个点的标记 以及 3.询问标记点在树上连通所需的最短总边权
数据范围：
点数以及操作数：1e5，边权：1e9（意思就是答案要 long long 存）。
分析：
这道题比赛的时候看的是真懵逼。。。
表示只会 n^3 做法（最多会n^2），以及特殊形态（比如链或者菊花图）的骗分法。
然鹅正解大概是 $O(n log n)$ 的做法，和树搭上了关系，加上这数据范围...
于是正解真是这个复杂度。（看到标程的时候表示惊讶，我太弱了）
标算就是用的dfs序加上lca的算法（如题）
首先我们不考虑 2、3 操作，我们先考虑如果树上有 k 个点被标记了，我们要得到树上 k 个点连通图的最小总边权。
我们可以在纸上画出这棵树以及标记的点，然后我们从左到右把点连成一块。
这时我们发现每两个相邻的点之间（相当于dfs序）的距离加上最后一个点和第一个点的距离，和正好是答案的两倍。
也就是说，如果把这些标记点按照dfs序排成一列，首尾相连形成一个环的话，答案就是这个环相邻点距离之和除以二。
（这种东西考场上怎么做得出来嘛）
那么我们回到原题，如果用上面的方法暴力处理答案，那么复杂度是 $O(n^{2} log n)$ 的（还不如 我自己想到的 n^2 咧）。
那么我们结合加点删点特殊的性质，以此优化算法复杂度。
我们发现加点其实就是在原环两相邻点之间插入了一个新点，然后原来两个相邻点的贡献没了，但是多了新点与这两个点分别的贡献。
那么删点类似的，就是令原环中某个点与相邻的两个点之间的贡献删除，并且多了这两个点之间的距离的贡献。
于是我们就可以用一个set来维护标记点，然后每次求距离的时候要用到 lca。
（lca建议常数小的树剖，倍增效率感人，tarjan 的话比较冷门基本不考虑）
那么我们就可以愉快地抄敲代码了！
代码 ：
//by Judge
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define It set<int>::iterator
#define ll long long
using namespace std;
const int M=1e5+;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1,*p2;
inline int read(){ int x=;
char c=getchar(); while(!isdigit(c)) c=getchar();
for(;isdigit(c);c=getchar()) x=x*+c-''; return x;
} inline int cread(){ char c=getchar();
while(c!='+'&&c!='-'&&c!='?') c=getchar();
return c=='?'?:(c=='+'?:);
} char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(ll x,char chr='\n'){
if(C><<)Ot(); while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]=chr;
} int n,m,pat,tim,head[M],f[M],son[M]; ll ans,dis[M];
int siz[M],top[M],dep[M],dfn[M],p[M]; set<int> s;
struct Edge{ int to,val,nxt;
Edge(int v,int c,int x):to(v),val(c),nxt(x){} Edge(){}
}e[M<<];
inline void add(int u,int v,int c){
e[++pat]=Edge(v,c,head[u]),head[u]=pat;
e[++pat]=Edge(u,c,head[v]),head[v]=pat;
}
#define v e[i].to
void dfs(int u,int fa){
siz[u]=,f[u]=fa,dep[u]=dep[fa]+;
for(int i=head[u];i;i=e[i].nxt) if(v^fa){
dis[v]=dis[u]+e[i].val,
dfs(v,u),siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
} void dfs(int u){
dfn[u]=++tim,p[tim]=u;
if(!top[u]) top[u]=u; if(!son[u]) return ;
top[son[u]]=top[u],dfs(son[u]);
for(int i=head[u];i;i=e[i].nxt)
if(v^f[u]&&v^son[u]) dfs(v);
}
#undef v
inline int lca(int u,int v){
while(top[u]^top[v])
(dep[top[u]]>dep[top[v]])?
u=f[top[u]]:v=f[top[v]];
return dep[u]<dep[v]?u:v;
} inline ll get(int u,int v){
return dis[u]+dis[v]-dis[lca(u,v)]*;
} inline It L(It it){
return (it==s.begin())?--s.end():--it;
} inline It R(It it){
return (it==--s.end())?s.begin():++it;
}
int main(){
n=read();
for(int i=,u,v,c;i<n;++i)
u=read(),v=read(),
c=read(),add(u,v,c);
dfs(,),dfs(),m=read();
for(int opt,x,t;m;--m){
opt=cread(); It it;
if(opt==) print(ans/);
else if(opt==){ x=read();
if(s.size()){
it=s.lower_bound(dfn[x]);
if(it==s.end()) it=s.begin(); t=*L(it);
ans+=get(x,p[t])+get(x,p[*it])-get(p[t],p[*it]);
} s.insert(dfn[x]);
} else if(opt==){ x=read();
if(s.size()>){
it=s.find(dfn[x]),t=*L(it),it=R(it);
ans-=get(x,p[t])+get(x,p[*it])-get(p[t],p[*it]);
} s.erase(dfn[x]);
}
} return Ot(),;
}