「Race」权值

形式化题目

给定一棵 $N$ 个节点的树，节点编号 $0 \sim N-1$ ，每条边带非负权值。求一条简单路径，使路径上各边权值之和等于 $K$ ，且路径包含的边数最少；不存在这样的路径时输出 -1。

把「路径」翻译成结构化的对象：对点 $c$ 和点 $u$ ，记

$dep_c(u)$ ：树上 $c$ 到 $u$ 唯一路径的边权之和；
$cnt_c(u)$ ：这条路径包含的边数。

要求的量就是

\min\{\,cnt_x(y) \;:\; x \neq y,\ dep_x(y) = K\,\}.

当 $x \neq y$ 的路径经过 $c$ 时， $dep_c(x) + dep_c(y) = dep_x(y)$ 且 $cnt_c(x) + cnt_c(y) = cnt_x(y)$ ——这是后面所有推导的支点。

以样例 $N = 4,\ K = 3$ 为例，树为 $0-1$ （权 1）、 $1-2$ （权 2）、 $1-3$ （权 4），六个点对的全部数据如下：

点对	路径	权值和	边数	等于 $K=3$ ？
$(0,1)$	$0 \to 1$	1	1	❌
$(0,2)$	$0 \to 1 \to 2$	3	2	✅
$(0,3)$	$0 \to 1 \to 3$	5	2	❌
$(1,2)$	$1 \to 2$	2	1	❌
$(1,3)$	$1 \to 3$	4	1	❌
$(2,3)$	$2 \to 1 \to 3$	6	2	❌

只有 $(0,2)$ 的权和等于 3，边数为 2，所以输出 2。注意 $(0,2)$ 的路径经过点 $1$ ，而 $(0,3)$ 、 $(2,3)$ 也经过点 $1$ 却不合法——「按路径经过哪个点分类」正是下面点分治的落点。

暴力解法

思路

枚举起点 $s$ ，做一次 DFS 求出 $s$ 到所有点的距离 dis[] 与边数 cnt[]，再枚举终点 $t$ 检查 dis[t] == K，取最小的 cnt[t] 作为答案。

正确性来自树上路径的唯一性：任意点对 $(x,y)$ 的路径只在 $s = x$ （或 $s = y$ ）那一轮被完整走出来，不存在漏数或重复计入最优解的情况。

代码

暴力解不单独给出：它就是把正解代码里「求重心、分层、容斥/先查询后合并」的部分删掉，退化成「对每个点各做一次 DFS 收集 $(dep, cnt)$ ，再两两检查」的形态。本次任务明确要求不落盘 brute.cpp，因此正确性改用两种方式验证：真实数据 50 组输出与标准答案完全一致；另用一次性 $O(N^2)$ 脚本在 $N \leqslant 30$ 、边权含 $0$ 的随机树上对拍 3000 组，结果完全一致。

复杂度

时间： $O(N^2)$ （每个起点一次 DFS 扫描全部边）。
空间： $O(N)$ （每次 DFS 的距离与边数数组）。

瓶颈

瓶颈是每条路径都要被单独走一遍。 $N = 2 \times 10^5$ 时是 $2 \times 10^{10}$ 量级的边访问，而题目给的时限只有 1s。真正被用到的信息其实只有「经过某点的两条半路径能否拼成 $K$ 」，因此必须让一批路径在同一次遍历里被一起判定。

正解

关键观察

观察 1（拆路径）。 固定一个点 $c$ ，则所有经过 $c$ 的路径都可以拆成「 $c \to x$ 」和「 $c \to y$ 」两段。于是判定条件由一个二元关系降成两个到 $c$ 的标量：

dep_c(x) + dep_c(y) = K \quad\Longleftrightarrow\quad dep_c(y) = K - dep_c(x),

答案候选也随之变成 $cnt_c(x) + cnt_c(y)$ 。从 $c$ 出发 DFS 一趟，就能为所有经过 $c$ 的路径同时判定。

观察 2（不重不漏）。 只固定一个 $c$ 不够，因为不经过 $c$ 的路径还没被处理。用点分治分层：每层取当前分量的重心 $c$ ，统计所有经过 $c$ 的路径，然后删掉 $c$ ，把剩下的每块递归下去。任一点对的路径要么经过 $c$ （本层统计），要么两点落在删掉 $c$ 后的同一块里（更深层统计），两种情况互斥且穷尽。重心保证每块规模不超过一半，层数 $O(\log N)$ 。

观察 3（用数组代替哈希表）。 题目给出 $K \leqslant 10^6$ ，距离的取值范围很小，不必用哈希表。开一个定长数组

best[d] = \text{「已处理部分中到重心距离为 } d \text{ 的最少边数」},

对子树里的每个点 $u$ 只需读 best[K - dep[u]]，配对查询就是一次数组下标访问。因为查询只做加法 $cnt + best[K - dep]$ ，同一个 $d$ 的候选中边数最少的必然最优，所以每个 $d$ 只留最小值不会丢失最优解。

观察 4（先查询后合并）。 直接把重心所有子树的点一次性合并进 best 再查询，会把「两点同在一棵子树、路径根本不经过重心」的点对也算进来。所以子树必须先查询、后合并：扫描某棵子树时，best 里只有重心和更早处理过的子树。这同时顺带解决了「点和自己配对」——查询时自己还没进 best，不会读到自己的记录。

观察 5（剪枝）。 边权非负，所以子树内某点的 $dep$ 已超过 $K$ 时，它和它的所有后代都不可能再与任何点凑成 $K$ ，整枝丢弃。

思路

点分治的每一层做四件事：求重心、清空 best、逐棵子树「查询 + 合并」、删点后把邻居压栈。

以样例（ $K = 3$ ）为例，第一层的重心是点 $1$ ，三棵子树分别是 $\{0\}$ 、 $\{2\}$ 、 $\{3\}$ ：

flowchart TD
    A["分量 {0,1,2,3}，重心 1<br>best[0] = 0（重心自身）"] --> B["子树 {3}：首边权 4 > K = 3<br>整枝剪掉，不扫描"]
    B --> C["子树 {2}：dep=2, cnt=1<br>查 best[1] 为空 → 无候选，合并 best[2] = 1"]
    C --> D["子树 {0}：dep=1, cnt=1<br>查 best[2] = 1 → 候选 1 + 1 = 2"]
    D --> E["ans = 2；层末擦掉 best，删掉重心 1"]
    E --> F["剩下三个单点分量：无点对可统计，算法结束"]

图中每个方框是重心 1 这一层按邻接表顺序处理的一步。子树 $\{3\}$ 因首边权 4 超过 $K$ 被整枝丢弃；子树 $\{2\}$ 扫描时 best 里只有重心，查到的是空位，合并后 best[2] 才有值；子树 $\{0\}$ 扫描时才能在 best[2] 上查到候选 2。删掉重心 1 后剩下三个单点分量，没有点对可统计。

把 best 数组的演化逐步写出来（ $K=3$ ，∞ 表示该格为空）：

阶段	操作	`best[0]`	`best[1]`	`best[2]`	`best[3]`	当前答案
初始化	处理重心 1，登记 $dep=0$	0	∞	∞	∞	∞
子树 $\{3\}$	首边权 $4 > K$ ，整枝跳过（不出现任何读写）	0	∞	∞	∞	∞
扫描子树 $\{2\}$	点 2： $dep=2, cnt=1$ ，查 `best[1]` $=\infty$	0	∞	∞	∞	∞
合并子树 $\{2\}$	把 $cnt=1$ 写入 `best[2]`	0	∞	1	∞	∞
扫描子树 $\{0\}$	点 0： $dep=1, cnt=1$ ，查 `best[2]` $=1$ → 候选 $1+1=2$	0	∞	1	∞	2
合并子树 $\{0\}$	把 $cnt=1$ 写入 `best[1]`	0	1	1	∞	2
层末清理	擦掉 `touched` 里的下标，删重心 1	∞	∞	∞	∞	2

表格的列是 best 的四个格子，行是层内按邻接表顺序发生的事件。要观察的重点有两个：一是查询总发生在合并之前，所以点 0 只能看到重心和子树 $\{2\}$ ，看不到自己；二是 best 里存的是「最少边数」，同一距离出现更优值时才覆盖。

实现上有三处细节：

求重心：先从代表点做一次迭代式 DFS，用 order 边遍历边增长代替手写栈，再由后往前累加子树大小；然后从代表点沿「重儿子」下走，只要存在超过总量一半的分支就走过去，走不动时所在点即重心。注意父方向那一块（大小 $total - sz[cent]$ ）也要参与比较，否则重心会判错。
层末清理：best 每层都要变空，但整数组清空是 $O(K)$ 、层数 $O(\log N)$ ，代价不必要。代码用 touched 记录本层首次写入的下标，层末只还原这些格子，与整层清空等价。
迭代代替递归：分量栈 todo 和扫描栈 stack 都是显式列表，避免 Python 深链上的递归深度问题。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 树链异或和恰为 k 的最少边数：点分治，best[d] 记录已处理部分中距离 d 的最少边数。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll INF = 1LL << 30; // 边数上界（简单路径最多 n-1 条边）

ll n, k;
ll edge_cnt = 0;

std::vector<int> head; // head[u] 是 u 的第一条弧
std::vector<int> nxt, eto, ewt;
std::vector<char> removed;
std::vector<ll> par, sz, dist, best;
std::vector<ll> touch2;

void add_edge(int u, int v, int w) {
    eto.push_back(v); ewt.push_back(w); nxt.push_back(head[u]); head[u] = edge_cnt++;
}

// 求 root 所在分量的重心：删掉它以后，剩下的每一块规模都不超过总量的一半
ll centroid_of(ll root) {
    par[root] = root;
    sz[root] = 0;
    std::vector<ll> order;
    order.push_back(root);
    for (size_t idx = 0; idx < order.size(); idx++) { // 边遍历边增长
        ll u = order[idx];
        for (int e = head[u]; e != -1; e = nxt[e]) {
            ll v = eto[e];
            if (!removed[v] && v != par[u]) {
                par[v] = u;
                sz[v] = 0; // 先归零，倒序累加才是干净的
                order.push_back(v);
            }
        }
    }
    for (size_t idx = order.size(); idx-- > 0;) { // 子节点一定排在父节点后面
        ll u = order[idx];
        sz[u] += 1;
        if (u != root) sz[par[u]] += sz[u];
    }

    ll total = sz[root];
    ll cent = root;
    while (true) {
        ll heavy = -1, best_sub = 0;
        ll up = total - sz[cent]; // 父节点方向那一块的规模
        for (int e = head[cent]; e != -1; e = nxt[e]) {
            ll v = eto[e];
            if (!removed[v]) {
                ll sub = (v == par[cent]) ? up : sz[v];
                if (sub > best_sub) {
                    heavy = v;
                    best_sub = sub;
                }
            }
        }
        if (best_sub * 2 <= total) return cent; // 没有任何一块超过一半
        cent = heavy;
    }
}

// 点分治：返回边权和恰为 k 的简单路径的最少边数，不存在则返回 INF
ll min_edges() {
    removed.assign(n, 0);
    par.assign(n, 0);
    sz.assign(n, 0);
    dist.assign(n, 0);
    std::vector<ll> cnt(n, 0);
    best.assign(k + 1, INF); // best[d] = 已处理部分中距离为 d 的最少边数
    std::vector<ll> todo;
    todo.push_back(0);
    ll ans = INF;

    std::vector<ll> cur_dist;
    std::vector<ll> stack;

    while (!todo.empty()) {
        ll root = todo.back();
        todo.pop_back();
        if (removed[root]) continue; // 该点已在更早的层里当过重心
        ll cent = centroid_of(root);

        best[0] = 0; // 重心自身：距离 0，边数 0
        touch2.clear();
        touch2.push_back(0);
        for (int e = head[cent]; e != -1; e = nxt[e]) {
            ll v = eto[e];
            if (removed[v] || ewt[e] > k) continue; // 首边超过 k，整棵子树都凑不出 k
            // 扫描这棵子树：只看距离不超过 k 的点
            std::vector<ll> nodes;
            par[v] = cent;
            dist[v] = ewt[e];
            cnt[v] = 1;
            ll here = INF;
            stack.clear();
            stack.push_back(v);
            while (!stack.empty()) {
                ll u = stack.back();
                stack.pop_back();
                nodes.push_back(u);
                ll du = dist[u], cu = cnt[u];
                ll cand = cu + best[k - du]; // 与重心或更早的子树拼成经过重心的路径
                if (cand < here) here = cand;
                for (int e2 = head[u]; e2 != -1; e2 = nxt[e2]) {
                    ll x = eto[e2];
                    if (!removed[x] && x != par[u]) {
                        ll dx = du + ewt[e2];
                        if (dx <= k) { // 权值非负，更深的点只会更远，可整枝剪掉
                            par[x] = u;
                            dist[x] = dx;
                            cnt[x] = cu + 1;
                            stack.push_back(x);
                        }
                    }
                }
            }
            if (here < ans) ans = here;
            for (size_t t = 0; t < nodes.size(); t++) { // 本子树内部的两点留给更深层
                ll u = nodes[t];
                ll d = dist[u];
                if (cnt[u] < best[d]) {
                    if (best[d] == INF) touch2.push_back(d);
                    best[d] = cnt[u];
                }
            }
        }

        for (size_t t = 0; t < touch2.size(); t++) best[touch2[t]] = INF; // 只擦本层写过的格子
        removed[cent] = 1;
        for (int e = head[cent]; e != -1; e = nxt[e]) {
            if (!removed[eto[e]]) todo.push_back(eto[e]);
        }
    }
    return ans;
}

int main() {
    if (scanf("%lld %lld", &n, &k) != 2) return 0; // 空输入安全返回
    head.assign(n, -1);
    nxt.reserve(2 * n);
    eto.reserve(2 * n);
    ewt.reserve(2 * n);
    for (ll i = 0; i < n - 1; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    ll ans = min_edges();
    printf("%lld\n", ans < INF ? ans : -1);
    return 0;
}

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150#!/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-10-01 19:10
# update_at: 2026-10-01 19:10

import sys
from array import array

INF = 1 << 30  # 边数上界（简单路径最多 n-1 条边）：best 的空位和「无解」都记成它


def centroid_of(head: array, nxt: array, to: array, removed: bytearray,
                par: array, sz: array, root: int) -> int:
    """求 root 所在分量的重心：删掉它以后，剩下的每一块规模都不超过总量的一半。"""
    par[root] = root
    sz[root] = 0
    order = [root]                                 # order 边遍历边增长，等价于手写栈
    for u in order:
        e = head[u]
        while e != -1:
            v = to[e]
            if not removed[v] and v != par[u]:
                par[v] = u
                sz[v] = 0                          # 先归零，下一轮倒序累加才是干净的
                order.append(v)
            e = nxt[e]

    for u in reversed(order):                      # 子节点一定排在父节点后面，可后序累加
        sz[u] += 1
        if u != root:
            sz[par[u]] += sz[u]

    total = sz[root]
    cent = root
    while True:
        heavy, best_sub = -1, 0
        up = total - sz[cent]                      # 父节点方向那一块的规模
        e = head[cent]
        while e != -1:
            v = to[e]
            if not removed[v]:
                sub = up if v == par[cent] else sz[v]
                if sub > best_sub:
                    heavy, best_sub = v, sub
            e = nxt[e]
        if best_sub * 2 <= total:                  # 没有任何一块超过一半：重心已找到
            return cent
        cent = heavy


def scan_subtree(head: array, nxt: array, to: array, wt: array, removed: bytearray,
                 par: array, dist: array, cnt: array, best: array,
                 k: int, cent: int, first: int, w0: int) -> tuple[list[int], int]:
    """扫描重心的一棵子树（首边权 w0），返回 (子树内的点, 子树内查到的最优边数)。

    只看距离不超过 k 的点；拼路径时查询的 best 只含重心和更早处理的子树，
    所以同一棵子树内部的两个点不会在此配成路径。
    """
    nodes: list[int] = []
    par[first], dist[first], cnt[first] = cent, w0, 1
    here = INF
    stack = [first]
    while stack:
        u = stack.pop()
        nodes.append(u)
        du, cu = dist[u], cnt[u]
        cand = cu + best[k - du]                   # 与重心或更早的子树拼成一条经过重心的路径
        if cand < here:
            here = cand
        e = head[u]
        while e != -1:
            x = to[e]
            if not removed[x] and x != par[u]:
                dx = du + wt[e]
                if dx <= k:                        # 权值非负，更深的点只会更远，可整枝剪掉
                    par[x], dist[x], cnt[x] = u, dx, cu + 1
                    stack.append(x)
            e = nxt[e]
    return nodes, here


def min_edges(head: array, nxt: array, to: array, wt: array, n: int, k: int) -> int:
    """点分治：返回边权和恰为 k 的简单路径的最少边数，不存在则返回 INF。"""
    removed = bytearray(n)
    par = array('i', bytes(4 * n))
    sz = array('i', bytes(4 * n))
    dist = array('i', bytes(4 * n))
    cnt = array('i', bytes(4 * n))
    best = array('i', [INF]) * (k + 1)             # best[d] = 已处理部分中距离为 d 的最少边数
    todo = [0]
    ans = INF

    while todo:
        root = todo.pop()
        if removed[root]:                          # 该点已在更早的层里当过重心
            continue
        cent = centroid_of(head, nxt, to, removed, par, sz, root)

        best[0] = 0                                # 重心自身：距离 0，边数 0
        touched = [0]
        e = head[cent]
        while e != -1:                             # 逐棵子树「先查询、后合并」，避免同子树配对
            v = to[e]
            if not removed[v] and wt[e] <= k:      # 首边就超过 k，整棵子树都不可能凑出 k
                nodes, here = scan_subtree(head, nxt, to, wt, removed, par, dist, cnt,
                                           best, k, cent, v, wt[e])
                if here < ans:
                    ans = here
                for u in nodes:                    # 本子树内部的两点留给更深层，此处只登记
                    d = dist[u]
                    if cnt[u] < best[d]:
                        if best[d] == INF:
                            touched.append(d)
                        best[d] = cnt[u]
            e = nxt[e]

        for d in touched:                          # 只擦本层写过的格子，免去每次 O(k) 清空
            best[d] = INF
        removed[cent] = 1
        e = head[cent]                             # 删掉重心：每个邻居各自代表一个新分量
        while e != -1:
            if not removed[to[e]]:
                todo.append(to[e])
            e = nxt[e]

    return ans


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

    # 链式前向星：head[u] 是 u 的第一条弧，每条无向边拆成方向相反的两条弧
    head = array('i', [-1]) * n
    to = array('i', bytes(8 * (n - 1)))
    wt = array('i', bytes(8 * (n - 1)))
    nxt = array('i', bytes(8 * (n - 1)))
    for i in range(0, 2 * (n - 1), 2):
        u, v, w = next(data), next(data), next(data)
        to[i], wt[i], nxt[i], head[u] = v, w, head[u], i
        to[i + 1], wt[i + 1], nxt[i + 1], head[v] = u, w, head[v], i + 1

    ans = min_edges(head, nxt, to, wt, n, k)
    print(ans if ans < INF else -1)


if __name__ == "__main__":
    solve()

复杂度

时间：每层每个点只被扫一次邻接表，该层总代价 $O(\text{分量规模})$ ；重心保证层数 $O(\log N)$ ，故总时间 $O(N \log N)$ 。与标准 C++ 点分治同阶。
空间：链式前向星（head 与 to/wt/nxt 共约 $7N$ 个 int）、best[0..K]、以及 $O(N)$ 的辅助数组，合计 $O(N + K)$ ， $N = 2 \times 10^5$ 、 $K = 10^6$ 时约 12MB。

总结

树上路径问题可以按「路径经过哪个点」分类：固定点 $c$ 后， $dep_c(x) + dep_c(y) = K$ 把「找一条路径」变成「配对两个到 $c$ 的距离」，一趟 DFS 就能批量判定。
点分治用重心保证递归深度 $O(\log N)$ ，用「删点后各块独立递归」保证每条路径只被统计一次；本层多算的恰好是同一子树内部的点对，用「先查询后合并」天然排除。
观察到 $K \leqslant 10^6$ 后，把「距离 → 最少边数」的映射放进定长数组而不是哈希表，配对查询变成一次下标访问，常数显著变小。
边权非负是（也是唯一需要的）剪枝依据： $dep > K$ 的整棵子树都不可能再参与配对。

「Race」 权值

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

思路

代码

复杂度

总结