Centroid decomposition

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int from;
    int to;
    int w;
};

struct node {
    int v;
    int d;
};

int const N = 333333;

vector<edge> edges[N];
vector<node> sv[N];
int sz[N], banned[N];
multiset<int> best[N];
int painted[N];

void dfs(int v, int p) {
    sz[v] = 1;
    for (edge & e : edges[v]) {
        if (e.to == p || banned[e.to]) continue;
        dfs(e.to, v);
        sz[v] += sz[e.to];
    }
}

void dfs2(int v, int p, int centroid, int d) {
    sv[v].push_back({centroid, d});
    for (edge & e : edges[v]) {
        if (e.to == p || banned[e.to]) continue;
        dfs2(e.to, v, centroid, d + e.w);
    }
}

void go(int v) {
    dfs(v, -1);
    int all = sz[v];
    {
        int pv = -1;
        while (true) {
            bool changed = false;
            for (edge & e : edges[v]) {
                if (e.to == pv || banned[e.to]) continue;
                if (sz[e.to] * 2 > all) {
                    pv = v;
                    v = e.to;
                    changed = true;
                    break;
                }
            }
            if (!changed) break;
        }
    }
    dfs2(v, -1, v, 0);
    banned[v] = true;
    for (edge & e : edges[v]) {
        if (!banned[e.to]) go(e.to);
    }
}

int const INF = 1 << 29;

int main() {
    freopen("treeeg.in", "r", stdin);
    freopen("treeeg.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 0; i + 1 < n; i++) {
        int v, u, l;
        scanf("%d%d%d", &v, &u, &l);
        --v;
        --u;
        edges[v].push_back({v, u, l});
        edges[u].push_back({u, v, l});
    }
    go(0);
    int q;
    scanf("%d", &q);
    painted[0] = true;
    for (node & e : sv[0])
        best[e.v].insert(e.d);
    for (int i = 0; i < q; i++) {
        int c = getchar();
        while (c <= 32) c = getchar();
        int v;
        scanf("%d", &v);
        --v;
        if (c == '?') {
            int ans = INF;
            for (node & e : sv[v]) {
                if (!best[e.v].empty())
                    ans = min(ans, e.d + *best[e.v].begin());
            }
            printf("%d\n", ans);
        } else if (c == '+') {
            if (!painted[v]) {
              for (node & e : sv[v]) {
                  best[e.v].insert(e.d);
              }
              painted[v] = true;
            }
        } else {
            if (painted[v]) {
              for (node & e : sv[v]) {
                  best[e.v].erase(best[e.v].find(e.d));
              }
              painted[v] = false;
            }
        }
    }
}