「Tree」树

形式化题目

给定一棵 $N$ 个点的带权树，点编号 $0 \sim N-1$ ，每条边的权值非负且不超过 $1000$ 。求无序点对 $(x, y)$ （ $x \neq y$ ）的个数，使得树上 $x$ 到 $y$ 的唯一路径的边权之和不超过 $K$ ；输入含多组测试用例，以 0 0 结束。

题目不保证 $K < N$ ，也不保证边权为正： $K$ 可以大于所有点对的距离之和，边权可以取 $0$ （数据范围 $N \leqslant 10000$ ，多组用例）。这两种情形都会影响计数的实现方式。

以样例 $N = 5,\ K = 4$ 的树为例，10 个点对的路径长度如下：

点对	路径	长度	$\leqslant 4$ ？
$(0,1)$	$0 \to 1$	3	✅
$(0,2)$	$0 \to 2$	1	✅
$(0,3)$	$0 \to 3$	2	✅
$(0,4)$	$0 \to 2 \to 4$	2	✅
$(1,2)$	$1 \to 0 \to 2$	4	✅
$(1,3)$	$1 \to 0 \to 3$	5	❌
$(1,4)$	$1 \to 0 \to 2 \to 4$	6	❌
$(2,3)$	$2 \to 0 \to 3$	3	✅
$(2,4)$	$2 \to 4$	1	✅
$(3,4)$	$3 \to 0 \to 2 \to 4$	4	✅

合法点对共 8 个，与样例输出一致。注意 $(2,4)$ 的路径不经过点 $0$ ，而 $(1,2)$ 的路径经过点 $0$ ——这个区别正是下面点分治容斥的落点。

暴力解法

思路

枚举每个点 $s$ 作为起点，做一次 DFS 求出它到所有点的距离，统计 $s < t$ 且 $dis(s,t) \leqslant K$ 的点对数。由于路径唯一且对称，每个无序点对恰被数一次，正确性显然。

代码

暴力解不单独给出：它就是正解代码去掉「求重心、分层、容斥」之后的退化形态——保留「从当前根 DFS 收集距离 + 统计距离和不超过 $K$ 的点对」，并对每个点都当作根跑一遍即可，验证也直接用正解代码完成。

复杂度

时间： $O(N^2)$ （每个起点一次 DFS）。
空间： $O(N)$ 。

瓶颈

瓶颈是每换一个起点就重扫整棵树： $N = 10^4$ 时是 $10^8$ 级别的边访问，而这还只是单组用例。要提速，就必须让「一批点对」在一次遍历里一起被统计，而不是一个起点一次。

正解

关键观察

观察 1：固定一个点 $c$ ，同时统计所有经过 $c$ 的路径。 若 $x, y$ 的路径经过 $c$ ，则 $dis(x,y) = dis(x,c) + dis(y,c)$ 。所以从 $c$ 出发 DFS 一趟，收集所有点到 $c$ 的距离，就能一次性判断「哪些点对经过 $c$ 且距离不超过 $K$ 」。

观察 2：按重心分层，不重不漏。 每次取当前分量的重心 $c$ 统计经过 $c$ 的路径，然后删掉 $c$ 、递归进剩下的分量。任一点对 $(x,y)$ 要么路径经过 $c$ （在本层被统计），要么 $x, y$ 落在删掉 $c$ 后的同一个分量里（在后续层被统计），两种情况互斥且穷尽。重心保证每个分量规模减半，递归深度 $O(\log N)$ 。

观察 3：本层的多余计数恰好是「同一子树内部」的点对。 只按 $dis(x,c) + dis(y,c) \leqslant K$ 统计，会把「两点同在 $c$ 的同一棵子树、路径不经过 $c$ 」的点对也算进来，需要减掉。这正是样例里 $(2,4)$ 与 $(1,2)$ 的区别。

思路

点分治的每一层做三件事：求重心、收集距离、容斥计数。

flowchart TD
    A["分量 {0,1,2,3,4}<br>重心 0：统计所有经过 0 的点对"] --> B["删 0 后分量 {1}"]
    A --> C["删 0 后分量 {3}"]
    A --> D["分量 {2,4}<br>重心 2：统计所有经过 2 的点对"]
    D --> E["删 2 后分量 {4}"]

图中每个方框是一层：先在重心处统计，再把删掉重心后的各分量作为下一层处理。样例树的重心依次是 $0$ 和 $2$ ；点对 $(1,2)$ 在第一层（经过 $0$ ）被统计，点对 $(2,4)$ 直到第二层（经过 $2$ ）才被统计，各出现一次。

求重心。 先从分量的代表点做一次迭代式 DFS，用 order 数组边遍历边增长代替手写栈，再由后往前累加子树大小。然后从代表点出发沿「重儿子」走：只要某个儿子的子树超过总点数一半，就走过去；走不动时所在点就是重心（它所有子树都不超过一半）。

收集距离。 从重心出发 DFS，把每个点到重心的距离记下来；超过 $K$ 的分支直接剪掉（边权非负，更深的点只会更远）。同时按「重心的那棵邻接子树」分桶，为容斥做准备。

计数。 对升序数组 $D$ ，满足 $d_i + d_j \leqslant K$ （ $i \leqslant j$ ）的点对数为

\text{cnt}(D) = \sum_i \#\{j \leqslant i : d_j \leqslant K - d_i\},

每个 $i$ 只需一次 bisect_right(D, K - d_i, 0, i + 1)。用二分而不是双指针，是因为本题 $K$ 可以大于所有距离、边权可以为 $0$ ，距离数组里会有大量相等值，二分的边界语义（「第一个大于」）不需要额外的单调性假设。

于是本层的贡献是

\text{cnt}(D_c) - \sum_{v \in \text{儿子}} \text{cnt}(D_v),

其中 $D_c$ 是所有点到重心的距离再加上重心自身的 $0$ ， $D_v$ 是第 $v$ 棵子树内各点到重心的距离。代码里 sub[0] 是重心自身的空占位，merged 就是 $D_c$ ，sub[1:] 就是各个 $D_v$ 。减掉的这些点对本层来说本来就不成立（路径不经过重心），它们会被递归到该子树时被正确统计。

用样例验证这一步（ $K = 4$ ，重心 $0$ ）： $D_c = \{0,1,2,2,3\}$ ，按 $i$ 从小到大，每个 $d_i$ 的前缀内合法个数为 $1,2,3,4,2$ ，合计 $\text{cnt}(D_c) = 12$ ；三棵子树（分别含点 $1$ 、点 $2,4$ 、点 $3$ ）的距离集合是 $\{3\}, \{1,2\}, \{2\}$ ，各自内部的 $\text{cnt}$ 为 $0, 3, 1$ ，合计 $4$ 。所以本层贡献 $12 - 4 = 8$ ：其中 7 个是路径经过点 $0$ 的合法点对 $(0,1),(0,2),(0,3),(0,4),(1,2),(2,3),(3,4)$ ，另 1 个是重心自己的自配对。

自配对修正。 计数时把重心自己的距离 $0$ 也算进了 $D_c$ ，因此每层会多算 1 个「点到它自己」的自配对；每个点恰好当过一次重心，共多算 $N$ 个。最后统一输出 divide(adj, k) - n。

代码

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/**
 * 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 的点对。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

ll N, K;

std::vector<std::vector<int> > g; // g[u]：u 出发的边编号
std::vector<int> eto, ewt;        // 边的另一端与边权
std::vector<char> removed;
std::vector<int> parent;
std::vector<ll> sz;
std::vector<ll> dists;            // 扫描子树时收集的距离
std::vector<int> order;

void add_edge(int u, int v, int w) {
    eto.push_back(v); ewt.push_back(w); g[u].push_back((int)eto.size() - 1);
    eto.push_back(u); ewt.push_back(w); g[v].push_back((int)eto.size() - 1);
}

// 求 root 所在分量的重心：删掉它后，剩下的每块规模都不超过总量一半
int find_centroid(int root) {
    int n = (int)g.size();
    parent.assign(n, -1);
    parent[root] = root;
    order.clear();
    order.push_back(root);
    for (size_t idx = 0; idx < order.size(); idx++) { // 边遍历边增长，等价于手写栈
        int u = order[idx];
        for (size_t j = 0; j < g[u].size(); j++) {
            int e = g[u][j];
            int v = eto[e];
            if (!removed[v] && v != parent[u]) {
                parent[v] = u;
                order.push_back(v);
            }
        }
    }

    for (size_t idx = order.size(); idx-- > 0;) { // 子节点一定排在父节点之后
        int u = order[idx];
        sz[u] = 1;
        for (size_t j = 0; j < g[u].size(); j++) {
            int e = g[u][j];
            int v = eto[e];
            if (!removed[v] && parent[v] == u) sz[u] += sz[v];
        }
    }

    int cent = root;
    ll total = sz[root];
    while (true) {
        int heavy = -1;
        ll best = 0;
        for (size_t j = 0; j < g[cent].size(); j++) {
            int e = g[cent][j];
            int v = eto[e];
            if (!removed[v] && parent[v] == cent && sz[v] > best) {
                heavy = v;
                best = sz[v];
            }
        }
        if (heavy < 0 || best * 2 <= total) return cent;
        cent = heavy;
    }
}

// 统计有序数组里有多少对 j <= i 满足 dist[j] + dist[i] <= k（含 i = j 的自配对）
ll count_le(std::vector<ll>& d, ll k) {
    ll total = 0;
    for (size_t i = 0; i < d.size(); i++) {
        ll lim = k - d[i];
        total += std::upper_bound(d.begin(), d.begin() + i + 1, lim) - d.begin();
    }
    return total;
}

ll divide() {
    int n = (int)g.size();
    removed.assign(n, 0);
    parent.assign(n, 0);
    sz.assign(n, 0);
    std::vector<int> roots;
    roots.push_back(0);
    ll answer = 0;

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

        int cent = find_centroid(root);

        // 从重心出发按子树收集距离（大于 k 的分支剪掉），sub[0] 是空占位（重心自身）
        std::vector<std::vector<ll> > sub;
        sub.push_back(std::vector<ll>());
        for (size_t j = 0; j < g[cent].size(); j++) {
            int e = g[cent][j];
            int v = eto[e];
            if (removed[v]) continue;
            std::vector<std::pair<int, std::pair<int, ll> > > stk;
            dists.clear();
            stk.push_back(std::make_pair(v, std::make_pair(cent, (ll)ewt[e])));
            while (!stk.empty()) {
                int u = stk.back().first;
                int par = stk.back().second.first;
                ll d = stk.back().second.second;
                stk.pop_back();
                if (d > K) continue; // 权值非负，更深的点只会更远
                dists.push_back(d);
                for (size_t t = 0; t < g[u].size(); t++) {
                    int e2 = g[u][t];
                    int x = eto[e2];
                    if (x != par && !removed[x]) { // 只看本子树 DFS 的父节点
                        stk.push_back(std::make_pair(x, std::make_pair(u, d + ewt[e2])));
                    }
                }
            }
            std::sort(dists.begin(), dists.end());
            sub.push_back(dists);
        }

        std::vector<ll> merged;
        merged.push_back(0);
        for (size_t s = 1; s < sub.size(); s++) {
            for (size_t t = 0; t < sub[s].size(); t++) merged.push_back(sub[s][t]);
        }
        std::sort(merged.begin(), merged.end());
        answer += count_le(merged, K);
        for (size_t s = 1; s < sub.size(); s++) {
            answer -= count_le(sub[s], K); // 同一子树内部的配对要在本层扣掉
        }

        removed[cent] = 1; // 删掉重心，邻居各代表一个新分量
        for (size_t j = 0; j < g[cent].size(); j++) {
            int e = g[cent][j];
            int v = eto[e];
            if (!removed[v]) roots.push_back(v);
        }
    }
    return answer;
}

int main() {
    std::vector<ll> out;
    while (scanf("%lld %lld", &N, &K) == 2) {
        if (N == 0 && K == 0) break;
        g.assign(N, std::vector<int>());
        eto.clear();
        ewt.clear();
        for (ll i = 0; i < N - 1; i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            add_edge(u, v, w);
        }
        // 计数包含 x = y 的自配对，而路径要求两个节点不同，故每个点各减一次
        out.push_back(divide() - N);
    }
    for (size_t i = 0; i < out.size(); i++) {
        printf("%lld\n", out[i]);
    }
    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#!/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 18:18
# update_at: 2026-10-01 18:27

import sys
from bisect import bisect_right


def count_le(sorted_dists: list[int], k: int) -> int:
    """统计有序数组里有多少对 j <= i 满足 dist[j] + dist[i] <= k（含 i = j 的自配对）。"""
    return sum(bisect_right(sorted_dists, k - d, 0, i + 1) for i, d in enumerate(sorted_dists))


def find_centroid(adj: list[list[tuple[int, int]]], removed: list[bool], root: int) -> int:
    """求 root 所在分量的重心：它删掉后，剩下的每块规模都不超过总量一半。"""
    n = len(adj)
    parent = [-1] * n
    parent[root] = root
    order = [root]
    for u in order:                                       # order 边遍历边增长，等价于手写栈
        for v, _ in adj[u]:
            if not removed[v] and v != parent[u]:
                parent[v] = u
                order.append(v)

    size = [0] * n
    for u in reversed(order):                             # 子节点一定排在父节点之后
        size[u] = 1
        for v, _ in adj[u]:
            if not removed[v] and parent[v] == u:
                size[u] += size[v]

    cent = root
    total = size[root]
    while True:
        heavy, best = -1, 0
        for v, _ in adj[cent]:
            if not removed[v] and parent[v] == cent and size[v] > best:
                heavy, best = v, size[v]
        if heavy < 0 or best * 2 <= total:                # 没有超过一半的重儿子：重心已找到
            return cent
        cent = heavy


def collect_by_subtree(
    adj: list[list[tuple[int, int]]], removed: list[bool], cent: int, k: int
) -> list[list[int]]:
    """从重心出发按子树收集距离（大于 k 的分支剪掉），sub[0] 是空占位，代表重心自身。"""
    sub: list[list[int]] = [[]]
    for v, w in adj[cent]:
        if removed[v]:
            continue
        dists: list[int] = []
        stack = [(v, cent, w)]
        while stack:
            u, p, d = stack.pop()
            if d > k:                                     # 权值非负，更深的点只会更远
                continue
            dists.append(d)
            stack += [(x, u, d + wx) for x, wx in adj[u] if x != p and not removed[x]]
        sub.append(sorted(dists))
    return sub


def divide(adj: list[list[tuple[int, int]]], k: int) -> int:
    """点分治：逐层在重心处用「汇总 - 各子树」容斥，返回合法点对数（含自配对）。"""
    n = len(adj)
    removed = [False] * n
    roots = [0]                                           # 待处理分量的代表点
    answer = 0

    while roots:
        root = roots.pop()
        if removed[root]:                                 # 该点已在更早的层里当过重心
            continue

        cent = find_centroid(adj, removed, root)
        sub = collect_by_subtree(adj, removed, cent, k)
        # 重心自身的距离 0 必 <= k，先加进汇总集合；同一子树内部的配对要在本层扣掉
        merged = sorted([0] + [d for ds in sub[1:] for d in ds])
        answer += count_le(merged, k) - sum(count_le(ds, k) for ds in sub[1:])

        removed[cent] = True                              # 分治层：删掉重心，邻居各代表一个新分量
        roots += [v for v, _ in adj[cent] if not removed[v]]

    return answer


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:
        n, k = next(data), next(data)
        if n == 0 and k == 0:
            break

        adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
        for _ in range(n - 1):
            u, v, w = next(data), next(data), next(data)
            adj[u].append((v, w))
            adj[v].append((u, w))

        # 计数包含 x = y 的自配对，而路径要求两个节点不同，故每个点各减一次
        out.append(str(divide(adj, k) - n))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

时间：每层分量总规模为 $N$ ，层数 $O(\log N)$ ；每层排序与二分各 $O(N \log N)$ ，总复杂度 $O(N \log^2 N)$ 。 $N = 10^4$ 时为 $10^6 \sim 10^7$ 量级基本操作。
空间：邻接表、removed、size、parent 均为 $O(N)$ ，每层的距离数组不跨层累积，总空间 $O(N)$ 。

总结

树上路径问题可以按「路径经过哪个点」分类统计；固定一个点 $c$ 后， $dis(x,y) \leqslant K$ 变成两个到 $c$ 的距离之和不超过 $K$ ，可在一趟 DFS 内批量判定。
点分治用重心保证递归深度 $O(\log N)$ ，用「删点后各分量独立递归」保证每个点对只被统计一次；本层多算的恰好是同一子树内部的点对，用容斥减掉。
计数用「排序 + 对每个 $d_i$ 二分 $K - d_i$ 」代替双指针，避免了边权为 $0$ 、 $K$ 大于所有距离时的边界陷阱，复杂度同阶。
实现上全部使用显式栈，不做递归调用，避免 Python 深树时的递归深度问题。

「Tree」 树

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

思路

代码

复杂度

总结