新人刚学OI 3 分钟，Pt30 求调QWQ

#include <bits/stdc++.h>
#define int long long
#define db double
#define N 200050
#define PII pair<int, int>
#define push push_back
#define popcnt(x) __builtin_popcountll(x)
const int INF = 4e18;
const int mod = 1e9 + 7;
using namespace std;

/*

1. 处理每个节点 u 的 dfn 与 lca
2. 使用 set 按 dfn 序储存已有的异象石
   ans 为 set 中相邻两个距离之和的一半(环状相邻)
   动态记录

*/

int n, m;
vector <PII> g[N];

int dep[N], dfn[N], tot;
int dis[N];
int p[N][21];

void dfs(int u, int fa){
	dfn[u] = ++tot;
	dep[u] = dep[fa] + 1;
	p[u][0] = fa;
	for(int i = 1; i <= 20; i++)
		p[u][i] = p[p[u][i - 1]][i - 1];
	for(auto ed : g[u]){
		int v = ed.first, w = ed.second;
		if(v == fa) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}

int lca(int u, int v){
	if(dep[u] > dep[v]) swap(u, v);
	for(int i = 20; i >= 0; i--)
		if(dep[p[v][i]] >= dep[u])
			v = p[v][i];
	if(u == v) return u;
	for(int i = 20; i >= 0; i--)
		if(dep[p[u][i]] != dep[p[v][i]])
			u = p[u][i], v = p[v][i];
	return p[u][0];
}

int get(int u, int v){
	return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}

struct node{
	int u;
	bool operator < (const node &a) const{
		return dfn[u] < dfn[a.u];
	}
};
set <node> st;
bool vis[N];

void solve(){
	cin >> n;
	for(int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;
		g[u].push({v, w}), g[v].push({u, w});
	}
	dfs(1, 0);
	cin >> m;
	int ans = 0;
	while(m--){
		char op; int u;
		cin >> op;
		if(op == '+' || op == '-'){
			cin >> u;
			node ins; ins.u = u;
			
			vis[u] ^= 1;
			if(vis[u]) st.insert(ins);
			
			auto it = st.find(ins);
			auto it1 = it, it2 = it;
			if(it1 == (st.begin())) it1 = --st.end();
			else it1--;
			if(it2 == (--st.end())) it2 = st.begin();
			else it2++;
			
			int l = (*it1).u, r = (*it2).u;
			int p = get(l, u) + get(u, r), q = get(l, r);
			
			if(vis[u]) ans = ans + p - q;
			else ans = ans - p + q;
			
			if(!vis[u]) st.erase(ins);
			
		} else cout << ans / 2 << '\n';
	}
}

signed main(){
	// freopen("c.in", "r", stdin);
	// freopen("c.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--)
        solve();
    return 0;
}