思路与算法

把所有异象石所在的点看作关键点，所求边集是包含这些点的最小连通子树。树边权为正，因此多取任何不必要的边都不能改善答案。

先以1为根，用显式栈遍历求每点DFS进入序、深度、根距离，并建立倍增祖先表。树上距离为 dist(u)+dist(v)-2*dist(lca(u,v))。

关键点按DFS序存入有序集合，并把最后一个与第一个也连起来，维护相邻关键点距离的总和 perimeter。答案是 perimeter/2。

插入x时，只需寻找循环前驱a和后继b，把原来的距离(a,b)替换成距离(a,x)+距离(x,b)。删除执行反向变更，再移除x。查询直接输出维护值的一半。空集合和单点集合的答案为0，单点删除后要清空总和。

正确性说明

任取树边，将树分成两侧。DFS进入序中，该边下方子树的点构成连续区间。若关键点只在一侧，按DFS序形成的环不跨越该边；若两侧都有关键点，循环序列恰有两次从一侧进入另一侧，因而距离总和恰好计入该边两次。

包含全部关键点的最小连通子树，恰由两侧均有关键点的边组成。因此环长等于最优子树总长度的两倍。插入和删除只改变循环中的相邻关系，代码对三项距离的增减正好保持此环长，故每次询问都正确。

复杂度

设点数为n、事件数为m、当前关键点数为s。邻接表、深度和进入序等数组初始化及遍历需O(n)，倍增表初始化和预处理需O(n log(n+1))时间与空间。有序集合每次插入删除和前驱后继查询为O(log(s+1))，常数次LCA距离查询为O(log(n+1))；问号事件O(1)。总时间O((n+m) log(n+1))，总空间O(n log(n+1))。

易错点

根距离和环长均使用long long，最大链的距离可接近10^14，环长还会加倍。DFS必须产生真正的子树连续进入序；程序用栈完整处理一个分支再处理其兄弟。循环前驱后继要处理集合首尾，删除唯一元素不能访问空集合。原题保证不会重复插入或删除不存在的关键点。n=1、空集、单点和树根作为关键点都合法。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Tree {
    int n, L, timer = 0;
    vector<vector<pair<int, ll>>> g;
    vector<vector<int>> up;
    vector<int> d, tin, rev;
    vector<ll> dist;
    Tree(int n) : n(n), L(1), g(n + 1), d(n + 1), tin(n + 1), rev(n + 1), dist(n + 1) {
        while ((1 << L) <= n)
            ++L;
        up.assign(L, vector<int>(n + 1));
    }
    void add(int u, int v, ll w = 1) {
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    void build() {
        vector<int> st(1, 1);
        up[0][1] = 1;
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            tin[u] = ++timer;
            rev[timer] = u;
            for (auto e : g[u])
                if (e.first != up[0][u]) {
                    int v = e.first;
                    up[0][v] = u;
                    d[v] = d[u] + 1;
                    dist[v] = dist[u] + e.second;
                    st.push_back(v);
                }
        }
        for (int k = 1; k < L; ++k)
            for (int u = 1; u <= n; ++u)
                up[k][u] = up[k - 1][up[k - 1][u]];
    }
    int lca(int u, int v) {
        if (d[u] < d[v])
            swap(u, v);
        int x = d[u] - d[v];
        for (int k = 0; k < L; ++k)
            if (x >> k & 1)
                u = up[k][u];
        if (u == v)
            return u;
        for (int k = L - 1; k >= 0; --k)
            if (up[k][u] != up[k][v])
                u = up[k][u], v = up[k][v];
        return up[0][u];
    }
    ll dis(int u, int v) {
        return dist[u] + dist[v] - 2 * dist[lca(u, v)];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    Tree t(n);
    for (int i = 1, u, v; i < n; ++i) {
        ll w;
        cin >> u >> v >> w;
        t.add(u, v, w);
    }
    t.build();
    int m;
    cin >> m;
    set<int> s;
    ll perimeter = 0;
    auto distance = [&](int a, int b) {
        return t.dis(t.rev[a], t.rev[b]);
    };
    while (m--) {
        char op;
        cin >> op;
        if (op == '?') {
            cout << perimeter / 2 << '\n';
            continue;
        }
        int x;
        cin >> x;
        x = t.tin[x];
        if (op == '+') {
            if (s.empty()) {
                s.insert(x);
                continue;
            }
            auto it = s.lower_bound(x);
            int b = it == s.end() ? *s.begin() : *it;
            int a = it == s.begin() ? *s.rbegin() : *prev(it);
            perimeter += distance(a, x) + distance(x, b) - distance(a, b);
            s.insert(x);
        } else {
            if (s.size() == 1) {
                s.clear();
                perimeter = 0;
                continue;
            }
            auto it = s.find(x), nxt = next(it);
            int b = nxt == s.end() ? *s.begin() : *nxt;
            int a = it == s.begin() ? *s.rbegin() : *prev(it);
            perimeter -= distance(a, x) + distance(x, b) - distance(a, b);
            s.erase(it);
        }
    }
}