[NOIP2007-提高] 树网的核

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

两次 BFS 求直径，按到两端距离之和等于直径筛出直径结点；每个结点挂到最近的直径结点上，直径上枚举长度不超过 s 的核并用滑动窗口维护窗口内最大挂接深度，偏心距取左露出、右露出与挂深三者的最大值。

OJ: roj

题目 ID: 3559

难度:提高

标签:

创建: 2026-10-02 07:37

更新: 2026-10-10 11:30

形式化题目

设 $T=(V,E,W)$ 是一棵无根树，边有正整数边权。 $d(a,b)$ 表示 $a,b$ 两点间唯一简单路径的边权之和。

对路径 $P$ 与结点 $v$ ，定义 $d(v,P)=\min\limits_{u \in P} d(v,u)$ ；
$\mathrm{ECC}(F)=\max\limits_{v \in V} d(v,F)$ ，即 $F$ 到全树最远结点的距离，称为 $F$ 的偏心距。

给定非负整数 $s$ ，要求在某条直径上取一段两端都是结点的子路径 $F$ （长度可退化为 $0$ ，即单个结点），使得 $F$ 的长度不超过 $s$ ，且 $\mathrm{ECC}(F)$ 最小。输出这个最小的偏心距。

正解

思路

第一步：把问题收缩到直径上。 设某条直径为 $u_0 \to \dots \to u_k$ ，长度为 $D$ 。任取核 $F$ ，由三角不等式（树上距离就是路径长，直接成立）：

树上任意一点到 $F$ 的距离，不超过它到 $F$ 所在直径上更远一端的距离。具体地：位于 $u_i$ 左侧（朝 $u_0$ 一侧）的结点到 $F$ 的距离 $\leqslant$ 核左端到 $u_0$ 的距离，记 $\text{left}=pos(i)$ ；右侧同理记 $\text{right}=D-pos(j)$ ；
于是 $\mathrm{ECC}(F) \leqslant \max(\text{left},\ \text{right},\ \text{窗口内挂深})$ 。取等号的最坏情形可以在直径端点处取到，所以直径上长度为 $\min(s, D)$ 的整段核本身就是一个可行解，最优值不会小于从直径上选出候选核后按该式算出的最小值。

因此只需在这条直径上枚举候选核即可。

第二步：求直径与直径结点。 经典两次 BFS：在树上，离任意一点最远的结点必是某条直径的端点。先从结点 $1$ BFS 得到最远点 $u_0$ ，再从 $u_0$ BFS 得到最远点 $u_k$ ， $d(u_0,u_k)$ 就是直径长 $D$ 。 $n \leqslant 300$ ，干脆对每个结点都做一次 BFS 存下全源距离表，后面直接查表，代码最短。

第三步：筛出直径结点。 结点 $x$ 在直径 $u_0 \to u_k$ 上，当且仅当

d(x,u_0)+d(x,u_k)=D

（必要：直径路径上按定义成立；充分：若 $d(x,u_0)+d(x,u_k)>D$ 与 $u_0 \to u_k$ 是直径矛盾，小于则拼接出比直径更长的路径）。把满足条件的结点按 $d(x,u_0)$ 排序，就得到直径上的结点序列 $path[0..k-1]$ ， $pos[t]=d(path[t],u_0)$ 。

第四步：把每个结点"挂"到直径上。 结点 $v$ 到核 $F$ 的路径，与直径的交点必是直径上离 $v$ 最近的结点（树上路径唯一，路径先走到直径、再沿直径走到 $F$ ；交点唯一是因为核在直径上且树上路径唯一）。定义

$v$ 的挂点： $path[t]$ ，使 $d(v,path[t])$ 最小（可证这样的 $t$ 唯一——若最小值在相邻两处打平，会拼出比直径更长的路径）；
$v$ 的挂接深度： $d(v,\text{挂点})$ 。

窗口内所有挂点的深度取 $\max$ ，就是核内一侧的贡献；核两侧"露出"的直径段贡献 $\text{left}$ 与 $\text{right}$ 。于是候选核 $[i..j]$ 的偏心距为

\mathrm{ECC} = \max\Big(\underbrace{pos(i)}_{\text{左侧露出}}，\ \underbrace{D-pos(j)}_{\text{右侧露出}}，\ \underbrace{\max_{i \leqslant t \leqslant j} dep[t]}_{\text{窗口内挂深}}\Big)

其中 $dep[t]$ 是挂在 $path[t]$ 上的最大挂接深度。

第五步：滑窗枚举。 枚举左端 $i$ ，右端 $j$ 随 $i$ 增大单调不减（ $pos$ 随 $t$ 递增），因此用双指针保证 $pos(j)-pos(i) \leqslant s$ ，同时维护窗口内 $dep$ 的最大值，逐个候选算 $\max$ 三元组，取全局最小。整体复杂度由 $n$ 次 BFS 主导。

样例 2 的直径与核

这张图展示样例 2 中两次 BFS 找到的直径，黄色结点按位置排成直径：

graph LR
    1 ==>|2| 3
    2 ---|2| 3
    3 ==>|6| 4
    4 ---|3| 5
    4 ---|4| 6
    4 ==>|2| 7
    7 ==>|3| 8
    style 8 fill:#ffe08a
    style 7 fill:#ffe08a
    style 4 fill:#ffe08a
    style 3 fill:#ffe08a
    style 1 fill:#ffe08a

直径端点是 8 与 1，直径长度为 13；黄色结点 [8, 7, 4, 3, 1] 依次位于直径的位置 [0, 3, 5, 11, 13]。观察发现：非黄色结点 2、5、6 的路径都先经过某个黄色结点（它们的挂点），偏心距只需关心这些挂点的深度，以及核两端露出的直径长度。

结点 v	挂点 path[t]	位置 t	挂接深度
2	3	3	2
5	4	2	3
6	4	2	4

这张表只列出非直径结点的挂接情况：挂接深度就是该结点到挂点的距离。当 s = 6 时，最优核是结点 4 到 3 这一段，偏心距为 $\max(5, 2, 4)=5$ ，与样例输出一致（左露出为核左端 4 到直径端点 8 的距离，右露出为核右端 3 到端点 1 的距离，窗口内最大挂深来自结点 6）。

代码

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/**
 * 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
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, s;
vector<pair<int, int> > adj[305];   // (v, w)
int dist_from[305][305];            // dist_from[v-1][x] = x 到 v 的距离
int u0_, uk_;

// 树中离 src 最远的结点编号 + 各点到 src 的距离
void farthest(int src, int dist[]) {
    for (int i = 1; i <= n; i++) dist[i] = -1;
    dist[src] = 0;
    deque<int> q;
    q.push_back(src);
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (size_t i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first, w = adj[u][i].second;
            if (dist[v] < 0) { dist[v] = dist[u] + w; q.push_back(v); }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back(make_pair(b, w));
        adj[b].push_back(make_pair(a, w));
    }

    // 两次 BFS 定位直径
    farthest(1, dist_from[0]);
    int far1 = 1;
    for (int i = 2; i <= n; i++)
        if (dist_from[0][i] > dist_from[0][far1]) far1 = i;
    u0_ = far1;
    farthest(u0_, dist_from[0]);   // dist0
    int far2 = u0_;
    for (int i = 1; i <= n; i++)
        if (dist_from[0][i] > dist_from[0][far2]) far2 = i;
    uk_ = far2;
    int dist0[305], distK[305];
    for (int i = 1; i <= n; i++) dist0[i] = dist_from[0][i];
    farthest(uk_, distK);
    int diameter = dist0[uk_];

    // 直径上的结点，按位置排序
    vector<int> path;
    for (int x = 1; x <= n; x++)
        if (dist0[x] + distK[x] == diameter) path.push_back(x);
    sort(path.begin(), path.end(), [&](int a, int b) { return dist0[a] < dist0[b]; });
    int k = (int)path.size();
    vector<int> pos(k);
    for (int t = 0; t < k; t++) pos[t] = dist0[path[t]];

    // 全源距离
    for (int v = 1; v <= n; v++) farthest(v, dist_from[v - 1]);

    // depAt[t]：以 path[t] 为挂点的结点的最大距离
    vector<int> depAt(k, 0);
    for (int v = 1; v <= n; v++) {
        int near = 0;
        int best = 1 << 30;
        for (int t = 0; t < k; t++) {
            int dd = dist_from[v - 1][path[t]];
            if (dd < best) { best = dd; near = t; }
        }
        depAt[near] = max(depAt[near], dist_from[v - 1][path[near]]);
    }

    // 枚举候选核 [i..j]
    int ans = diameter;
    int j = 0;
    for (int i = 0; i < k; i++) {
        if (j < i) j = i;
        while (j + 1 < k && pos[j + 1] - pos[i] <= s) j++;
        int cover = 0;
        for (int t = i; t <= j; t++) cover = max(cover, depAt[t]);
        int left_tail = pos[i];
        int right_tail = diameter - pos[j];
        ans = min(ans, max(cover, max(left_tail, right_tail)));
    }
    cout << ans << "\n";
    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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
from collections import deque


def farthest(adj: list[list[tuple[int, int]]], src: int) -> tuple[int, list[int]]:
    """返回树中离 src 最远的结点编号，以及各结点到 src 的距离（树上路径唯一，BFS 即最短路）。"""
    dist = [-1] * len(adj)
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[v] < 0:
                dist[v] = dist[u] + w
                dq.append(v)
    far = max(range(1, len(adj)), key=dist.__getitem__)
    return far, dist


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

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

    # 两次 BFS 定位直径：树上离任一点最远的点必是某条直径的端点
    u0, _ = farthest(adj, 1)
    uk, dist0 = farthest(adj, u0)
    _, distK = farthest(adj, uk)
    diameter = dist0[uk]

    # 满足 d(u0,x)+d(x,uk)=diameter 的 x 恰是直径上的结点，按位置排序
    path = sorted((x for x in range(1, n + 1) if dist0[x] + distK[x] == diameter), key=dist0.__getitem__)
    pos = [dist0[x] for x in path]  # pos[t]：直径第 t 个结点在直径上的位置
    k = len(path)

    # n ≤ 300，直接对每个结点做一次 BFS 得全源距离
    dist_all = [farthest(adj, v)[1] for v in range(1, n + 1)]

    # depAt[t]：以 path[t] 为"挂点"（到直径路径最近的直径结点）的结点的最大距离
    # 结点 v 的路径与直径交于唯一点，argmin 唯一给出挂点，最小值即挂接深度
    depAt = [0] * k
    for v in range(1, n + 1):
        near = min(range(k), key=lambda t: dist_all[v - 1][path[t]])
        depAt[near] = max(depAt[near], dist_all[v - 1][path[near]])

    # 枚举直径上的候选核 [i..j]（长度 ≤ s），双指针保证 j 只增不减
    # 窗口外两侧结点的距离被 pos[i]、diameter-pos[j] 支配（可证 挂深 ≤ 挂点到较远端点的长）
    ans = diameter
    j = 0
    for i in range(k):
        if j < i:
            j = i
        while j + 1 < k and pos[j + 1] - pos[i] <= s:
            j += 1
        cover = max(depAt[i : j + 1])  # 窗口内挂点深度
        left_tail = pos[i]             # 直径左端到核左端的距离
        right_tail = diameter - pos[j]  # 直径右端到核右端的距离
        ans = min(ans, max(cover, left_tail, right_tail))

    print(ans)


if __name__ == "__main__":
    solve()

复杂度

时间：对每个结点做一次 BFS 为 $O(n^2)$ （ $n \leqslant 300$ ，全源距离表约 $9 \times 10^4$ 项）；双指针扫直径为 $O(n)$ ，总复杂度 $O(n^2)$ ，与标准 C++ 解法同阶。
空间：全源距离表 $O(n^2)$ 。

总结

本题是经典的"树的直径 + 核"模型，核心链条是三次收缩：

求直径：两次 BFS 定端点，用 $d(x,u_0)+d(x,u_k)=D$ 筛出直径结点；
挂点分解：每个结点到核的路径必先经过直径上离它最近的结点，把"全树到核的最远距离"拆成"左右露出的直径长度"与"窗口内最大挂接深度"两个可局部维护的量；
滑窗枚举：候选核的左右端点在直径上都是单调的，双指针加窗口最大值即可。

$n \leqslant 300$ 的规模允许直接建全源距离表，省去求 LCA 或树形 DP 的复杂度，是这道题最舒服的实现方式。该模型向 $n$ 更大的版本推广时，用 DFS 树形 DP 或双 BFS 求直径、前缀最大值维护挂深，思路不变。

题目描述

设 $T=(V,E,W)$ 是一个无圈且连通的无向图（也称为无根树），每条边到有正整数的权，我们称 $T$ 为树网（treebetwork），其中 $V$ ， $E$ 分别表示结点与边的集合， $W$ 表示各边长度的集合，并设 $T$ 有 $n$ 个结点。

路径：树网中任何两结点 $a$ ， $b$ 都存在唯一的一条简单路径，用 $d(a, b)$ 表示以 $a, b$ 为端点的路径的长度，它是该路径上各边长度之和。我们称 $d(a, b)$ 为 $a, b$ 两结点间的距离。

$D(v, P)=\min\{d(v, u)\}$ , $u$ 为路径 $P$ 上的结点。

树网的直径：树网中最长的路径成为树网的直径。对于给定的树网 $T$ ，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距 $\mathrm{ECC}(F)$ ：树网T中距路径F最远的结点到路径 $F$ 的距离，即

$\mathrm{ECC}(F)=\max\{d(v, F),v \in V\}$

任务：对于给定的树网 $T=(V, E, W)$ 和非负整数 $s$ ，求一个路径 $F$ ，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 $s$ （可以等于s），使偏心距 $ECC(F)$ 最小。我们称这个路径为树网 $T=(V, E, W)$ 的核（Core）。必要时， $F$ 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

下面的图给出了树网的一个实例。图中， $A-B$ 与 $A-C$ 是两条直径，长度均为 $20$ 。点 $W$ 是树网的中心， $EF$ 边的长度为 $5$ 。如果指定 $s=11$ ，则树网的核为路径DEFG（也可以取为路径DEF），偏心距为 $8$ 。如果指定 $s=0$ （或 $s=1$ 、 $s=2$ ），则树网的核为结点 $F$ ，偏心距为 $12$ 。

输入输出格式

输入格式：

共 $n$ 行。

第 $1$ 行，两个正整数 $n$ 和 $s$ ，中间用一个空格隔开。其中 $n$ 为树网结点的个数， $s$ 为树网的核的长度的上界。设结点编号以此为 $1,2,…,n$ 。

从第 $2$ 行到第 $n$ 行，每行给出 $3$ 个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“ $2 4 7$ ”表示连接结点 $2$ 与 $4$ 的边的长度为 $7$ 。

输出格式：

一个非负整数，为指定意义下的最小偏心距。

输入输出样例

输入样例#1：

5 2 1 2 5 2 3 2 2 4 4 2 5 3

输出样例#1：

输入样例#2：

8 6 1 3 2 2 3 2 3 4 6 4 5 3 4 6 4 4 7 2 7 8 3

输出样例#2：

说明

$40\%$ 的数据满足： $5 \le n \le 15$
$70\%$ 的数据满足： $5 \le n \le 80$
$100\%$ 的数据满足： $5 \le n \le 300,0 \le s \le 1000$ 。边长度为不超过 $1000$ 的正整数

NOIP 2007 提高第四题