centroid decomposition

#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <memory.h>
#include <algorithm>
#include <stack>
#include <deque>
#include <iomanip>
#include <stdio.h>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <iterator>
#include <chrono>
#include <array>
#include <bitset>
#define pii pair <int, int>
#define debug(x) cerr << (#x) << " " << (x) << endl
#define pb push_back
#define all(vc) vc.begin(), vc.end()
#define endl "\n"
using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int LOGN = 19, INF = (long long)(1e9) + 7;

vector<int> sz;
vector<bool> used;
vector<int> d;
vector<int> sum;
vector<vector<pii>> sp;
vector<int> idx;
vector<int> euler;
vector<int> logn;

int size(vector<vector<pii>>& gr, int v, int pr = -1) {
    sz[v] = 1;
    for (auto i : gr[v]) {
        int u = i.first;
        if (u != pr && !used[u]) {
            sz[v] += size(gr, u, v);
        }
    }
    return sz[v];
}

int centroid(vector<vector<pii>>& gr, int v, int n, int pr) {
    for (auto i : gr[v]) {
        int u = i.first;
        if (u == pr) {
            continue;
        }
        if (sz[u] > n / 2 && !used[u]) {
            return centroid(gr, u, n, v);
        }
    }
    used[v] = 1;
    return v;
}

vector<int> p;

void decomposition(vector<vector<pii>>& gr, int n, int k, int v, int pr = -1, int cntr = -1) {
    sz.resize(n);
    size(gr, v);

    int cnt = centroid(gr, v, n / k, pr);
    p[cnt] = cntr;
    k *= 2;

    for (auto i : gr[cnt]) {
        int u = i.first;
        if (u == pr || used[u]) {
            continue;
        }
        decomposition(gr, n, k, u, cnt, cnt);
    }
    return;
}

void dfs(vector<vector<pii>>& gr, int v, int pr, int cost = 0) {
    d[v] = d[pr] + 1;
    sum[v] = sum[pr] + cost;
    idx[v] = (int)(euler.size());
    euler.push_back(v);
    for (auto& u : gr[v]) {
        if (u.first != pr) {
            dfs(gr, u.first, v, u.second);
        }
        euler.push_back(v);
    }
}

int get_lca(int v, int u) {
    int l = min(idx[u], idx[v]), r = max(idx[u], idx[v]);
    int lvl = logn[r - l + 1];
    pii ans = min(sp[lvl][l], sp[lvl][r - (1LL << lvl) + 1]);
    return ans.second;
}

int get_sum(int u, int v) {
    int lca = get_lca(u, v);
    if (lca == u) {
        return sum[v] - sum[u];
    }
    if (lca == v) {
        return sum[u] - sum[v];
    }
    return sum[u] + sum[v] - 2 * sum[lca];
}

void insert(vector<multiset<int>>& st, int v) {
    int u = v;
    while (u != -1) {
        st[u].insert(get_sum(u, v));
        u = p[u];
    }
}

void erase(vector<multiset<int>>& st, int v) {
    int u = v;
    while (u != -1) {
        st[u].erase(st[u].find(get_sum(u, v)));
        u = p[u];
    }
}

int get_ans(vector<multiset<int>>& st, int v) {
    int ans = INF;
    int u = v;
    while (u != -1) {
        if (!st[u].empty()) {
            int len = *st[u].begin();
            len += get_sum(u, v);
            ans = min(ans, len);
        }
        u = p[u];
    }
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));

    int n;
    cin >> n;
    vector<vector<pii>> gr(n);
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        gr[a].push_back({ b, c });
        gr[b].push_back({ a, c });
    }

    used.resize(n);
    sz.resize(n);
    size(gr, 0);

    p.resize(n, -1);
    decomposition(gr, n, 1, 0);
    used = vector<bool>(0);
    d.resize(n);
    sum.resize(n);
    idx.resize(n);
    dfs(gr, 0, 0);
    gr = vector<vector<pii>>(0);

    logn.resize((int)(euler.size()) + 1);
    logn[1] = 0;
    for (int i = 2; i <= (int)(euler.size()); i++) {
        logn[i] = logn[i / 2] + 1;
    }

    sp.resize(logn[(int)(euler.size())] + 1, vector<pii>((int)(euler.size())));
    for (int i = 0; i < euler.size(); i++) {
        sp[0][i] = { d[euler[i]], euler[i] };
    }
    for (int i = 1; (1 << i) <= euler.size(); i++) {
        for (int j = 0; j + (1LL << i) <= euler.size(); j++) {
            sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1LL << (i - 1))]);
        }
    }

    vector<multiset<int>> st(n);
    insert(st, 0);
    int q;
    cin >> q;

    while (q--) {
        char type;
        cin >> type;
        int v;
        cin >> v;
        v--;

        if (type == '+') {
            insert(st, v);
        }
        else if (type == '-') {
            erase(st, v);
        }
        else {
            cout << get_ans(st, v) << endl;
        }
    }
    return 0;
}