「一本通 4.4 例 2」暗的连锁

GitHub跳转原题关系图返回列表

树上差分统计每条主要边被几条附加边跨越，按 0/1/≥2 三类累加 M/1/0，倍增求 LCA。

OJ: roj

题目 ID: 1553

难度:提高

标签:LCA树上差分倍增树python

创建: 2026-09-30 17:43

更新: 2026-10-07 12:15

前置题目

luogu P3258[JLOI2014] 松鼠的新家B 的树上差分（main.py 中 diff[u]++、diff[v]++、diff[w]-=2 加 reversed(order) 后序累加求父边跨越次数）正是 A 教的“求 lca 后对两端点打差分、自底向上累加统计路径经过次数”这一步，只是把 LCA 的减标记从点差分改成边差分 -=2，再叠加 c_e 的 0/1/≥2 三分类计数。luogu P3128[USACO15DEC] Max Flow PB 的树边跨越计数直接复用 A 教的树上差分：路径加一先化成差分端点并在 LCA 处抵消，再统一后序累加，只是把点差分换成边差分并叠加三分类统计。luogu P9246[蓝桥杯 2023 省 B] 砍树B 的树上差分逐字复用 A 教的「diff[u]++、diff[v]++、diff[w]-=2」端点打标记与自底向上累加求父边跨越次数这一步，只是把统计对象换成附加边路径，再叠加 c_e 的 0/1/>=2 三分类计数。

后置题目

roj 3189雨天的尾巴B 处理每条路径的第一步直接复用 A 教的「求 LCA 后对路径端点打差分、在 LCA 处抵消再子树汇总」这一树上差分步骤，只是把 A 的边差分 diff[w]-=2 换成点差分 lca 与 father(lca) 各 -1，再叠加权值线段树合并与众数查询。luogu P1600[NOIP 2016 提高组] 天天爱跑步B 的 main.cpp 把每条玩家路径拆成两段后挂 event_up/event_down 的 +1/-1 事件，正是 A 教的「用 LCA 做端点加、LCA 处抵消的树上差分，再后序累加」这一步，只是把数值累加换成两个桶的前后读数之差，并叠加 A 未教的「到达时刻写成深度等式→特征值入桶」维度，故为提高→省选/NOI- 的台阶式前置。luogu P3833[SHOI2012] 魔法树B 的 add_path 直接复用 A 教的「先求 LCA、再在端点处打差分标记让路径加在 LCA 抵消」这一步，只是把 A 的边差分 diff[w]-=2 改写成点差分 diff[p]-=d、diff[parent(p)]-=d，再叠加子树和展开与两棵树状数组。

形式化题目

给定一个 $N$ 个节点的无向图，由两类边组成：

$N-1$ 条主要边构成一棵树（任意两点间恰有一条只走主要边的路径）；
$M$ 条附加边。

按规则切两条边：先切一条主要边，之后主要边无敌、只能再切一条附加边（即使第一步已把图切断，也必须切）。问有多少种"（第一条主要边，第二条附加边）"的有序方案，使最终图不连通。

以样例 $N=4,\ M=1$ 为例，主要边 $(1,2),(2,3),(1,4)$ 、附加边 $(3,4)$ ，样例的树与虚线附加边如下：

graph TD
    n1["1"] --- n2["2"]
    n2 --- n3["3"]
    n1 --- n4["4"]
    n3 -.- n4

切主要边 $(1,2)$ 后 $\{1,4\}$ 与 $\{2,3\}$ 两半只靠附加边 $(3,4)$ 相连，切掉它即断开；同理切 $(2,3)$ 、 $(1,4)$ 后也都只剩附加边 $(3,4)$ 这一条连接，各对应 1 种方案，共 $1+1+1=3$ ，与样例输出一致。

正解

思路

朴素做法先暴露瓶颈。 枚举每条主要边 $e$ ：切断它，树断成两半 $A,B$ ；再枚举 $M$ 条附加边数出跨 $A,B$ 的条数 $c_e$ 。关键是第二步切完后图不连通的条件：

切完第一条后两半内部各是一棵树（树边都在各自半边内），所以内部永远连通，第二步切内部边不影响断开；
整图连通当且仅当还剩至少一条跨 $A,B$ 的附加边。

于是对每条主要边 $e$ 按 $c_e$ 三分类：

$c_e$ （跨边数）	第二步可切的附加边	贡献
$0$	图已断开，题面仍要求切一条， $M$ 条任选都保持断开	$M$
$1$	只有切掉那条唯一的跨边才能断开	$1$
$\geqslant 2$	切一条至少还剩一条，两半始终相连	$0$

答案就是 $\sum_{e} \big(c_e = 0 ?\ M :\ c_e = 1 ?\ 1 :\ 0\big)$ 。

瓶颈与翻转。 朴素做法对每条树边重新数一遍跨边，总 $O(N(N+M))$ ；而所有 $c_e$ 其实由 $M$ 条附加边决定——每条附加边 $(u,v)$ 会给路径 $u \to v$ 上的每条树边 $+1$ 。把问题翻转成"枚举附加边、路径加，最后统一收集"，就是经典的树上差分：

设 $w = \mathrm{lca}(u,v)$ ，对差分数组（代码中的 diff）做 $\mathrm{diff}[u] {+}{+},\ \mathrm{diff}[v] {+}{+},\ \mathrm{diff}[w] {-}{-} 2$ （两个端点的流在 LCA 处抵消）；
对树按后序累加（代码中倒序遍历先根列表 reversed(order)），孩子 $x$ 上累加完的 diff[x] 恰好等于边 $(\mathrm{fa}[x], x)$ 被跨越的次数，即这条边的 $c_e$ ；累加时顺手做三分类求和。

每条附加边只花一次 LCA 的 $O(\log N)$ （倍增求法：先抬深度，再从高到低同步上跳），全部差分 $O(M\log N)$ ；一次倒序回溯同时完成累加和三分类求和， $O(N)$ 。整体 $O((N+M)\log N)$ ，与 C++ 正解同阶。

以样例走一遍：附加边 $(3,4)$ 的路径是 $3 \to 2 \to 1 \to 4$ ，三条主要边各被跨越一次， $c_e$ 全为 1，按表格每条贡献 1，得 $1+1+1=3$ 。

代码

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#!/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:43
# update_at: 2026-09-30 17:43

import sys

LOG = 17  # 倍增上跳层数：2^17 = 131072 > N 上限 1e5


def lca(u: int, v: int, depth: list[int], up: list[list[int]]) -> int:
    """倍增求 u、v 的最近公共祖先。"""
    if depth[u] < depth[v]:
        u, v = v, u
    # 先把更深的 u 抬到与 v 同一深度
    d = depth[u] - depth[v]
    for k in range(LOG):
        if d >> k & 1:
            u = up[k][u]
    if u == v:
        return u
    # 两者不同则同步上跳，跳到 LCA 的正下方
    for k in range(LOG - 1, -1, -1):
        if up[k][u] != up[k][v]:
            u, v = up[k][u], up[k][v]
    return up[0][u]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 主要边构成树：无向邻接表
    g: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        a, b = next(data), next(data)
        g[a].append(b)
        g[b].append(a)

    # 以 1 为根迭代 DFS（避免深递归）：记父亲、深度与先根顺序
    root = 1
    parent = [0] * (n + 1)
    parent[root] = root
    depth = [0] * (n + 1)
    order: list[int] = []
    stack = [root]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in g[u]:
            if v != parent[u]:
                parent[v] = u
                depth[v] = depth[u] + 1
                stack.append(v)

    # 倍增表：up[k][v] 是 v 的 2^k 级祖先；先根顺序保证父亲先于孩子处理
    up = [[0] * (n + 1) for _ in range(LOG)]
    up[0] = parent[:]
    for k in range(1, LOG):
        prev, cur = up[k - 1], up[k]
        for v in order:
            cur[v] = prev[prev[v]]

    # 树上差分：一条附加边 (u, v) 使路径上每条主要边的跨越计数 +1
    diff = [0] * (n + 1)
    for _ in range(m):
        u, v = next(data), next(data)
        w = lca(u, v, depth, up)
        diff[u] += 1
        diff[v] += 1
        diff[w] -= 2

    # 后序累加得到每条主要边的跨越计数 c，按 c 统计方案数
    ans = 0
    for u in reversed(order):
        if u == root:
            continue
        c = diff[u]  # 边 (parent[u], u) 被多少条附加边跨越
        ans += m if c == 0 else (1 if c == 1 else 0)
        diff[parent[u]] += c  # 计数并入父边

    print(ans)


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/**
 * 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:50
 * update_at: 2026-10-05 07:50
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // 节点数上限 1e5
const int LOG = 17;      // 2^17 = 131072 > 1e5，倍增跳 depth 最多用到第 16 位

// 主要边构成一棵树，用链式前向星存无向边（每条边加两次）
int head[MAXN];      // head[u]：u 的第一条出边编号，-1 表示无边
int to[2 * MAXN];    // to[e]：第 e 条边的终点
int nxt[2 * MAXN];   // nxt[e]：第 e 条边的下一条兄弟边
int edge_cnt = 0;

int parent[MAXN]; // parent[v]：v 在根为 1 的树上的父亲，根的父亲为 0
int depth[MAXN];  // depth[v]：v 到根的边数
int order[MAXN];  // order[i]：迭代 DFS 第 i 个出栈的节点（先根顺序）
int order_cnt = 0;

int up[LOG][MAXN]; // up[k][v]：v 向上跳 2^k 步到达的祖先

int diff[MAXN]; // diff[u] 树上差分：后序累加后等于边 (parent[u], u) 被附加边跨越的次数，不超过 M=2e5，用 int 即可

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 以 1 为根迭代 DFS，求出 parent、depth 和先根序 order（避免递归爆栈）
void build_tree(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = 0;
    }
    parent[1] = 0;
    depth[1] = 0;
    order_cnt = 0;

    int stack[MAXN];
    int top = 0;
    stack[++top] = 1;
    while (top > 0) {
        int u = stack[top--];
        order_cnt++;
        order[order_cnt] = u;
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u]) {
                continue;
            }
            parent[v] = u;
            depth[v] = depth[u] + 1;
            stack[++top] = v;
        }
    }
}

// 在树上预处理倍增表：up[k][v] = up[k-1][ up[k-1][v] ]
void build_up(int n) {
    for (int v = 1; v <= n; v++) {
        up[0][v] = parent[v];
    }
    for (int k = 1; k < LOG; k++) {
        for (int v = 1; v <= n; v++) {
            up[k][v] = up[k - 1][up[k - 1][v]];
        }
    }
}

// 倍增求 u、v 的最近公共祖先
int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        int t = u;
        u = v;
        v = t;
    }
    // 先把更深的 u 抬到与 v 同深度
    int d = depth[u] - depth[v];
    for (int k = 0; k < LOG; k++) {
        if ((d >> k) & 1) {
            u = up[k][u];
        }
    }
    if (u == v) {
        return u;
    }
    // 再让两者同步上跳，停在 LCA 的正下方
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    }
    return up[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        head[i] = -1;
    }
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
        add_edge(b, a);
    }

    build_tree(n);
    build_up(n);

    // 每条附加边 (u, v) 会给树上路径 u->v 上的每条主要边 +1，
    // 用树上差分：diff[u]++, diff[v]++, diff[lca(u,v)] -= 2
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int w = lca(u, v);
        diff[u]++;
        diff[v]++;
        diff[w] -= 2;
    }

    // 按先根序倒序（即后序）累加差分，得到每条主要边的跨越次数 c：
    //   c == 0：第一步已断开，第二步 M 条附加边任选，贡献 M
    //   c == 1：只能切那条唯一的跨边，贡献 1
    //   c >= 2：怎么切都还连通，贡献 0
    ll ans = 0;
    for (int i = order_cnt; i >= 1; i--) {
        int u = order[i];
        if (u == 1) {
            continue;
        }
        int c = diff[u];
        if (c == 0) {
            ans += m;
        } else if (c == 1) {
            ans += 1;
        }
        diff[parent[u]] += c; // 把这条边的跨越次数并入父边
    }

    cout << ans << "\n";

    return 0;
}

复杂度

时间复杂度： $O((N+M)\log N)$ 。建图与两次遍历 $O(N)$ ，倍增表 $O(N\log N)$ ， $M$ 次 LCA 差分 $O(M\log N)$ 。
空间复杂度： $O(N\log N)$ ，倍增表 $17(N+1)$ 加邻接表与差分数组；实测峰值约 83.7 MB，在 128 MB 限制内。

总结

三分类是本题的核心观察： $c_e = 0$ 贡献 $M$ （图已断但必须再切一条，切哪条都行）、 $c_e = 1$ 贡献 $1$ 、 $c_e \geqslant 2$ 贡献 $0$ ；正确性依赖"两半内部是树、永远连通"这一性质。
“按边枚举、查跨边"要翻转成"按附加边枚举、路径加”：树上差分 $d[u] {+}{+}, d[v] {+}{+}, d[w] {-}{-} 2$ 配一次后序累加， $O(1)$ 完成一条附加边的全部贡献。
LCA 用倍增、遍历用迭代栈，规避 Python 递归深度限制；实测 10 组真实数据全部一致，最大一组 0.512 s、峰值 83.7 MB，本地相对 20 s 放宽限时毫无压力（OJ 限时 1000 ms 下 Python 有 TLE 风险，按约定允许）。

【题目描述】

原题来自：POJ 3417

Dark 是一张无向图，图中有 $N$ 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 $N–1$ 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark 还有 MM 条附加边。

你的任务是把 Dark 斩为不连通的两部分。一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

【输入】

第一行包含两个整数 $N$ 和 $M$ ；

之后 $N – 1$ 行，每行包括两个整数 $A$ 和 $B$ ，表示 $A$ 和 $B$ 之间有一条主要边；

之后 $M$ 行以同样的格式给出附加边。

【输出】

输出一个整数表示答案。

【输入样例】

text

【输出样例】

text

【提示】

数据范围与提示：

对于 20% 的数据， $1≤N,M≤100$ ；

对于 100% 的数据， $1≤N≤10^5 ,1≤M≤2×10^5$ 。数据保证答案不超过 $2^{31}-1$ 。

【来源】

一本通在线评测

「一本通 4.4 例 2」暗的连锁

目录

形式化题目

正解

思路

代码

复杂度

总结