「一本通 4.4 例 3」异象石

形式化题目

给定一棵 $N$ 个点的带权无向树，动态度量点集。要求支持：

向点集中加入一个当前不在集合中的点；
从点集中删除一个当前在集合中的点；
询问当前点集在树上的斯坦纳树（包含这些点及其两两路径并集的最小子树）的边权之和；点集大小不超过 1 时答案为 $0$ 。

正解

思路

第一步：把"连通所有异象石"翻译成斯坦纳树

"使点集 $S$ 中所有点连通的最小边集"只有一种取法： $S$ 中任意两点之间的路径都必须出现在边集中，所以最小边集正是这些路径的并集，也就是 $S$ 在树上的斯坦纳树，答案就是它的边权和。 $|S| \le 1$ 时没有边需要选，答案为 $0$ 。

第二步：朴素做法及其瓶颈

斯坦纳树长度可以用 DFS 序算出来。把 $S$ 中的点按进入时刻 $\mathrm{tin}$ 从小到大排成环 $a_1, a_2, \dots, a_k$ （约定 $a_{k+1} = a_1$ ），则

\text{答案} \;=\; \frac{1}{2}\sum_{i=1}^{k} \operatorname{dist}(a_i,\; a_{i+1}).

于是朴素做法是：每次询问重新枚举整个 $S$ 、排序、逐对求 LCA 距离，单次 $O(|S| \log N)$ 。 $M$ 次询问最坏 $O(NM \log N)$ ，显然会超时。

瓶颈很清楚：每次询问都在重算整个环，而一次操作其实只改变一个点。 只要想到"环上只有 $O(1)$ 条相邻边会变"，复杂度立刻降下来。

第三步：为什么 DFS 序能给出斯坦纳树

先说明上面那个恒等式为什么成立，否则后面的增量维护没有依据。

考虑斯坦纳树上的任意一条边 $e$ 。删掉 $e$ 后树被切成两侧，其中一侧（记作子树 $T_e$ ）里含有一部分异象石。记 $T_e$ 中异象石的 $\mathrm{tin}$ 集合为 $P_e$ 。

关键字是： $P_e$ 恰好是一段连续的区间。因为子树 $T_e$ 中的点在 DFS 序里是连续访问的。于是把环上的点依次走一遍，进入区间 $P_e$ 一次、离开它一次，恰好跨越割 $(T_e, \bar T_e)$ 两次。

每一次跨越都对应环上某条相邻边 $a_i \to a_{i+1}$ ，而 $\operatorname{dist}(a_i, a_{i+1})$ 这条路径必然经过 $e$ 。所以 $e$ 一共被环上相邻距离之和累加了 $2 w_e$ 。对斯坦纳树的每条边求和，就得到

\sum_{i=1}^{k} \operatorname{dist}(a_i, a_{i+1}) \;=\; 2 \cdot (\text{斯坦纳树边权和}).

这正是第二步的公式。这个证明同时也解释了为什么必须用 DFS 序：只有 DFS 序才能保证"子树的点连续成段"，换任何一种遍历序都会让某条边被跨越超过两次，从而算出偏大的结果。

以样例树为例（以 1 为根，括号内是 $\mathrm{tin}$ ）：

text

1
2
3
4
5              1 (tin=1)
            / | \
   (tin=6) 2  3 (tin=5)  4 (tin=2)
                         / \
                (tin=4) 5   6 (tin=3)

DFS 序为 $1,4,6,5,3,2$ 。当 $S=\{1,3,6\}$ 时，按 $\mathrm{tin}$ 排成的环是 $1 \to 6 \to 3 \to 1$ ，相邻距离依次为

相邻对	路径	距离
$1 \to 6$	$1\!-\!4\!-\!6$	$7+2=9$
$6 \to 3$	$6\!-\!4\!-\!1\!-\!3$	$2+7+5=14$
$3 \to 1$ （首尾闭合）	$3\!-\!1$	$5$

环和 $=9+14+5=28$ ，折半得 $14$ ，与样例第三组输出一致。

第四步：增量维护

设 $x$ 在有序序列中的位置为 $i$ ，前驱为 $p$ 、后继为 $s$ （都按环取模）。

插入 $x$ ：环上原来直接相连的是 $(p, s)$ ，现在被 $x$ 断成 $(p,x)$ 与 $(x,s)$ 。环和的变化量是

$\Delta = \operatorname{dist}(p,x) + \operatorname{dist}(x,s) - \operatorname{dist}(p,s).$
删除 $x$ ：正是上式的逆操作，环和减去同一个 $\Delta$ 。

两处公式完全一样，只有加减号不同，实现时可以共用同一段表达式。这样每个操作只需 3 次 LCA 距离计算， $O(\log N)$ 。

第五步：维护有序序列与 LCA

有序序列用 Python 的 list 维护 $\mathrm{tin}$ ，bisect_left 定位后用 insert / pop 搬移。搬移是 C 层的 memmove，常数极小，实测 $10^5$ 规模完全够用。
用 (i - 1)（Python 负数下标自动绕到环尾）和 (i + 1) % len(order)（绕回环首）统一处理首尾相邻，不需要特判。
LCA 用倍增表：jump[k][v] 表示 $v$ 的第 $2^k$ 级祖先，预处理 $O(N\log N)$ ，单次查询 $O(\log N)$ 。距离用 $d_u + d_v - 2 d_{\mathrm{lca}}$ ，其中 $d$ 是根到点的距离。
DFS 必须迭代实现：树可能退化成链，深度 $10^5$ 会让 Python 递归直接爆栈。根到点距离在 DFS 访问子节点时立即赋值，不能等 DFS 结束后再遍历边表补算（父边可能排在子边之后）。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 17:59
# update_at: 2026-09-30 18:08

import sys
from bisect import bisect_left

ADD = 43      # 事件首字节 '+'：点 x 上出现异象石
QUERY = 63    # 事件首字节 '?'：询问连通所有异象石的最短边集长度
              # 删除（首字节 '-'）是默认分支，不单独登记


def euler_tour(
    head: list[int], nxt: list[int], to: list[int], weight: list[int], n: int
) -> tuple[list[int], list[int], list[int], list[int]]:
    """迭代 DFS，返回 (进入时刻 tin, 深度 dep, 父节点 up, 根到点的距离 root_dist)。

    用显式栈代替递归：树可以退化成链，深度 10^5 会让 Python 递归直接爆栈。
    tin 随进入顺序单调递增，所以"按 tin 排序"就是"按 DFS 序排序"。
    """
    tin, dep, up = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
    root_dist = [0] * (n + 1)
    timer = 0
    stack = [(1, head[1])]
    while stack:
        u, e = stack.pop()
        if e == -1:                       # 边扫完了：u 的子树处理结束
            continue
        if e == head[u]:                  # 第一次弹出 u：登记进入时刻
            timer += 1
            tin[u] = timer
        stack.append((u, nxt[e]))         # 压回"接着扫 u 的下一条邻边"
        v = to[e]
        if v != up[u]:                    # 不沿来路边走回父亲
            up[v] = u
            dep[v] = dep[u] + 1
            root_dist[v] = root_dist[u] + weight[e]   # 父节点的距离此刻已经算好
            stack.append((v, head[v]))
    return tin, dep, up, root_dist


def build_up(up: list[int], n: int, levels: int) -> list[list[int]]:
    """倍增表 jump[k][v] = v 的第 2^k 级祖先；节点 0 是根的父亲，作哨兵。"""
    jump = [up]
    for _ in range(levels - 1):
        prev = jump[-1]
        jump.append([prev[prev[v]] for v in range(n + 1)])
    return jump


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())

    n = int(next(data))

    # 链式前向星：head[u] 是 u 的第一条边，nxt[e] 是共享 u 的下一条边
    head = [-1] * (n + 1)
    to: list[int] = []
    nxt: list[int] = []
    weight: list[int] = []
    for _ in range(n - 1):
        x, y, z = int(next(data)), int(next(data)), int(next(data))
        to += [y, x]
        weight += [z, z]
        nxt += [head[x], head[y]]
        head[x] = len(to) - 2
        head[y] = len(to) - 1

    tin, dep, up, root_dist = euler_tour(head, nxt, to, weight, n)
    levels = max(1, n.bit_length())
    jump = build_up(up, n, levels)

    def lca(u: int, v: int) -> int:
        """倍增求最近公共祖先。"""
        if dep[u] < dep[v]:
            u, v = v, u
        diff = dep[u] - dep[v]
        for k in range(levels):
            if diff >> k & 1:
                u = jump[k][u]
        if u == v:
            return u
        for k in range(levels - 1, -1, -1):
            if jump[k][u] != jump[k][v]:
                u, v = jump[k][u], jump[k][v]
        return up[u]

    # 欧拉序的时刻 -> 节点，用于把环上的前驱后继还原成节点编号
    rev = [0] * (n + 2)
    for v in range(1, n + 1):
        rev[tin[v]] = v

    def dist(u: int, v: int) -> int:
        """树上两点距离 = 根距离之和 - 2 * 根到 LCA 的距离。"""
        w = lca(u, v)
        return root_dist[u] + root_dist[v] - 2 * root_dist[w]

    order: list[int] = []   # 当前所有异象石按 tin 升序排列
    # total 是欧拉环上相邻距离之和，它恰好是答案（最小连通边集长度）的两倍：
    # 环游一圈会把斯坦纳树的每条边正反各走一次，所以输出时折半。
    total = 0
    out: list[str] = []

    m = int(next(data))
    for _ in range(m):
        kind = next(data)[0]
        if kind == QUERY:
            out.append(str(total // 2))       # 偶数，整除无舍入
            continue

        x = int(next(data))
        i = bisect_left(order, tin[x])
        if kind == ADD:                           # 把环上 (前驱, 后继) 换成 (前驱, x) + (x, 后继)
            order.insert(i, tin[x])
            prev = rev[order[i - 1]]                  # -1 绕回环尾
            next_node = rev[order[(i + 1) % len(order)]]  # 只有一个元素时指向自己
        else:                                     # '-'：先取出删掉后占住 i 的后继，再弹出 x
            next_node = rev[order[(i + 1) % len(order)]]
            prev = rev[order[i - 1]]
            order.pop(i)
        # 插入加、删除减，增量公式完全一致
        delta = dist(prev, x) + dist(x, next_node) - dist(prev, next_node)
        total += delta if kind == ADD else -delta

    sys.stdout.write('\n'.join(out) + ('\n' if out else ''))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:52
 * update_at: 2026-10-05 07:52
 */
#include <cstdio>
#include <set>
#include <utility>
using namespace std;

/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 12:41
 * update_at: 2026-10-04 12:41
 */

// 异象石：动态度维护点集在树上的斯坦纳树边权和。
// 核心：把点集按 DFS 序(tin)排成环，环上相邻距离之和 = 2 * 斯坦纳树长度。
// 插入/删除一个点只改环上 O(1) 条相邻边，用有序表 + 倍增 LCA 增量维护。

typedef long long ll;

const int MAXN = 100005;   // n, m <= 1e5
const int LOG = 17;        // 2^17 > 1e5，倍增层数

// 链式前向星存树
int head[MAXN];   // head[u]：u 的第一条边编号
int nxt[2 * MAXN]; // nxt[e]：与边 e 同起点的下一条边
int to_[2 * MAXN]; // to_[e]：边 e 的终点
ll wt[2 * MAXN];   // wt[e]：边 e 的长度（z 可达 1e9，用 ll）
int edge_cnt;

int n, m;
int tin[MAXN];    // tin[u]：DFS 进入时刻，即 DFS 序排名
int dep[MAXN];    // dep[u]：深度
int up[MAXN];     // up[u]：父亲节点（0 为根的哨兵父亲）
ll dis[MAXN];     // dis[u]：根到 u 的距离（边长和可达 1e14，用 ll）
int node_of_tin[MAXN]; // node_of_tin[t]：DFS 序第 t 个位置的节点编号
int jump[LOG][MAXN];   // jump[k][v]：v 的第 2^k 级祖先

// 有序表：当前异象石按 tin 升序
set<int> order;   // 存每个异象石的 tin
// total：环上相邻距离之和 = 2 * 当前答案（环游每条斯坦纳树边恰走两次）
ll total;

// 加一条双向边
void add_edge(int u, int v, ll w) {
    edge_cnt++;
    to_[edge_cnt] = v;
    wt[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 迭代 DFS 求 tin / dep / up / dis。
// 树可能退化成链，深度 1e5，递归会爆栈，必须用显式栈。
// 栈元素 (u, e)：u 尚未扫完的邻边从 e 开始；e == 0 表示 u 的边已扫完。
void dfs_tin() {
    pair<int, int> stk[MAXN];
    int top = 0;
    int timer = 0;

    up[1] = 0;
    dep[1] = 0;
    dis[1] = 0;
    stk[top++] = make_pair(1, head[1]);
    while (top > 0) {
        int u = stk[top - 1].first;
        int e = stk[top - 1].second;
        if (e == 0) { // u 的邻边扫完，弹出
            top--;
            continue;
        }
        if (e == head[u]) { // 第一次处理 u：登记进入时刻
            timer++;
            tin[u] = timer;
            node_of_tin[timer] = u;
        }
        stk[top - 1].second = nxt[e]; // 接着扫 u 的下一条邻边
        int v = to_[e];
        if (v != up[u]) { // 不沿来路边走回父亲
            up[v] = u;
            dep[v] = dep[u] + 1;
            dis[v] = dis[u] + wt[e]; // 父亲的距离此刻已经算好
            stk[top++] = make_pair(v, head[v]);
        }
    }
}

// 倍增表预处理
void build_jump() {
    for (int v = 1; v <= n; v++) jump[0][v] = up[v];
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            jump[k][v] = jump[k - 1][jump[k - 1][v]];
}

// 倍增求最近公共祖先
int lca(int u, int v) {
    if (dep[u] < dep[v]) {
        int t = u; u = v; v = t;
    }
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = jump[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (jump[k][u] != jump[k][v]) {
            u = jump[k][u];
            v = jump[k][v];
        }
    return up[u];
}

// 树上两点距离 = 根距离之和 - 2 * 根到 LCA 的距离
ll dist(int u, int v) {
    int w = lca(u, v);
    return dis[u] + dis[v] - 2 * dis[w];
}

// 插入或删除点 x：环上 (前驱, 后继) 与 (前驱, x) + (x, 后继) 的差值大小相同。
// 插入加、删除减，共用同一段表达式。
void update_delta(int x, bool is_add) {
    set<int>::iterator it = order.find(tin[x]);
    // 环上找前驱、后继：首尾相接，只有一个元素时前驱后继都是自己
    int p, s;
    if (it == order.begin()) p = node_of_tin[*order.rbegin()];
    else p = node_of_tin[*(--it)]; // --it 之后 it 不再指向 tin[x]，下面重新 find
    it = order.find(tin[x]);
    it++;
    if (it == order.end()) s = node_of_tin[*order.begin()];
    else s = node_of_tin[*it];

    ll delta = dist(p, x) + dist(x, s) - dist(p, s);
    if (is_add) total += delta;
    else total -= delta;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) head[i] = 0;
    edge_cnt = 0;
    for (int i = 1; i < n; i++) {
        int x, y;
        ll z;
        scanf("%d %d %lld", &x, &y, &z);
        add_edge(x, y, z);
        add_edge(y, x, z);
    }

    dfs_tin();
    build_jump();

    scanf("%d", &m);
    total = 0;
    for (int i = 1; i <= m; i++) {
        char op[5];
        scanf("%s", op);
        if (op[0] == '?') {
            // 环长是答案的两倍，且必为偶数，整除无舍入；空集时 total = 0
            printf("%lld\n", total / 2);
        } else {
            int x;
            scanf("%d", &x);
            if (op[0] == '+') {
                order.insert(tin[x]);
                update_delta(x, true);
            } else { // '-'
                update_delta(x, false);
                order.erase(tin[x]);
            }
        }
    }
    return 0;
}

复杂度

预处理 $O(N \log N)$ ；一次插入或删除（含有序表搬移）为 $O(\log N + k)$ ， $k$ 是当前异象石数量；一次询问 $O(1)$ 。

总时间 $O\big(N \log N + M(\log N + k)\big)$ ，空间 $O(N \log N)$ （邻接表加倍增表）。

总结

核心恒等式：按 DFS 序排成环后，环长等于斯坦纳树的两倍（每条斯坦纳树边被跨越恰好两次）。
正因为环长是"两倍"，输出时别忘了折半；这是最容易漏掉、且会让所有答案翻倍的一步。
增量维护的立足点是局部性：一次操作只改环上 $O(1)$ 条相邻边，由此从"每次询问重算"降到"每次操作 $O(\log N)$ "。

图示解析

下图把本题的推导路线、实现分工和验证要点压缩到一处，适合读完正文后复盘。

flowchart TD
    A["点集 S 的斯坦纳树边权和"] --> B["按 tin 排成环 a1..ak"]
    B --> C["环长 = 2 x 斯坦纳树长度"]
    C --> D["答案 = 环长 / 2"]
    C --> E["增量维护: 插入/删除只改 (p,x),(x,s)"]
    E --> F["有序表 list + bisect_left"]
    E --> G["dist(u,v) = du + dv - 2*d_lca"]
    G --> H["倍增 LCA, 迭代 DFS 求 tin/dep/up/root_dist"]
    D --> I["? 直接输出 total // 2"]

方案分工：

环与有序表负责"答案是多少"，把一次操作压缩成常数次距离计算；
倍增 LCA 与迭代 DFS 是底层支撑，提供 $O(\log N)$ 的两点距离；
? 事件不做任何计算，只把已经维护好的 total 折半输出。

需要注意的三处边界： $S = \varnothing$ 时输出 $0$ ；插入第一个点时 $\Delta = 0$ ；同一元素先 + 后 - 能回到空集状态。