CH#56C 异象石

一道贼可怕的题目，这能想到就想到，不能想到就等着被算法题目（日常）揍吧。
另外这道题有参考别人代码之嫌，实属弟弟行为，下次一定不。
题目链接：良心网站acwing
题意：中文题啊=_=
思路：LCA+set维护，首先你得要理解时间戳的概念，对于出现的异象石你可以发现一个规律叫做按照时间戳排序，异象石的节点连成一个圈，并且累加相邻的节点，最后得到的结果恰好是路径和的两倍，这是本题最为可怕的地方，因为你根本想不到竟然还可以这样累加，我下次该怎么想这种题目？手画样例？还是默默的把这种结论记下来？很难考到这么奇怪的题目吧，叹息。另外本题有个地方你记下时间戳以后，对应的pos位置也要记录下来。这就完成了。

#define _CRT_SECURE_NO_WARNINGS 1
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define aint(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long LL;
typedef set<int>::iterator IT;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int N = 1e5+9 ,M = 1e6+1;
const int Maxn=1000010;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
///head
int n ,m ;
int head[N], edge[N<<1], Next[N<<1], ver[N<<1], tot;
int pos[N], dfn[N] ,vis[N];
int dep[N], fa[N][20];
LL dis[N][20] ,ans;
set<int>s;
void add(int x, int y , int z){
    ver[++tot] = y , edge[tot] = z , Next[tot] = head[x] , head[x] = tot;
}
int cnt ;
void bfs(){
    queue<int>q;
    q.push(1); vis[1] = 1; dep[1] = 1;
    while(q.size()){
        int x = q.front();q.pop();
        for(int i = head[x]; i ; i = Next[i]){
            int y = ver[i];
            if(vis[y])continue;
            vis[y] = 1;
            dep[y] = dep[x] + 1;
            fa[y][0] = x;
            dis[y][0] = edge[i];
            for(int j = 1 ; j < 20 ;j ++){
                fa[y][j] = fa[fa[y][j-1]][j-1];
                dis[y][j] = dis[fa[y][j-1]][j-1] + dis[y][j-1];
            }
            q.push(y);
        }
    }
}

LL lca(int x,int y){
    LL res = 0;
    if(dep[x] > dep[y])swap(x , y);
    for(int i = 19; i >= 0; i --)
        if(dep[fa[y][i]] >= dep[x])res += dis[y][i],y = fa[y][i];
    if(x == y) return res;
    for(int i = 19 ; i >= 0; i --)
    if(fa[x][i] != fa[y][i])
        res += dis[x][i] + dis[y][i] , x = fa[x][i], y = fa[y][i];
    return res + dis[x][0] + dis[y][0];
}

void dfs(int x,int fa = -1){
    dfn[x] = ++cnt, pos[cnt] = x;
    for(int i = head[x]; i ; i = Next[i]){
        int y = ver[i];
        if(y == fa) continue;
        dfs(y ,x);
    }
}
IT L(IT it)
{
	if(it==s.begin())return --s.end();
	return --it;
}
IT R(IT it)
{
	if(it==--s.end())return s.begin();
	return ++it;
}

int main(){
    while(~scanf("%d", &n )){
        memset(head, 0 , sizeof head);
        s.clear(); ans = 0;
        for(int i = 1; i < n ; i ++){
            int x, y , z;
            scanf("%d %d %d" ,&x, &y , &z);
            add(x,y,z);
            add(y,x,z);
        }
        dfs(1);
        bfs();
        scanf("%d" , &m);
        while(m --){
            char op[4] ;
            int ope ;
            scanf("%s",op);
            if(op[0] == '+'){
                scanf("%d" , &ope);
                if(SZ(s)){
                    auto it1 = s.lower_bound(dfn[ope]);
                    if(it1 == s.end()) it1 = s.begin();
                    auto it2 = L(it1);
                    ans += lca(ope, pos[*it2]) + lca(ope,pos[*it1]) - lca(pos[*it1],pos[*it2]);
                }
                s.insert(dfn[ope]);
            }
            else if(op[0] == '-'){
                scanf("%d" , &ope);
                auto it1 = s.find(dfn[ope]);
                auto it2 = L(it1);
                it1 = R(it1);
                ans -= lca(ope , pos[*it2]) + lca(ope, pos[*it1]) - lca(pos[*it2] , pos[*it1]);
                s.erase(dfn[ope]);
            }
            else{
                printf("%lld\n",ans / 2);
            }
        }
    }
}