形式化题目

给定一棵带非负边权的无根树与一个长度上界 $s$。树上一条简单路径称为"核"，若它的长度不超过 $s$，则它是"直径上的核"当且仅当它位于某条树的直径上。定义核 $F$ 的偏心距为所有节点到 $F$ 的距离的最大值。求所有直径上的核中偏心距的最小值。

样例图

用样例 in1 的树来看"直径"和"核"长什么样。黄色节点（1、2、4）构成直径 1-2-4，红色节点 2 是核（单点，长度 0 不超过 $s=2$），边上标出了权值：

先看这棵树的形状：从节点 2 出发连到 3、5 的两条分支不在直径上，它们的最大深度是 3。核取单点 2 时，偏心距 = max(节点 1 到 2 的距离 5, 节点 4 到 2 的距离 4, 分支深度 3) = 5，正是样例答案——后面所有公式都会落到这张图上。

暴力

先看一个完全按定义实现的暴力解：

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/**
 * 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-08-12 22:28
 * update_at: 2026-08-12 22:28
 */
// brute.cpp：小数据暴力解，枚举直径上的所有核区间，直接按定义计算偏心距。
// 教学点：不套任何偏心距公式，把"区间上每个节点都试一遍"当作距离定义，
// 用来验证 main.cpp 中 max(左距离, 右距离, 分支深度) 公式的正确性。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;

struct Edge {
    int v; // 邻居节点
    int w; // 边权
};

int n, s;               // n 个节点，核的长度上界 s
vector<Edge> g[MAXN];   // 邻接表存树

int far_dis[MAXN];      // far_dis[u]：本次搜索中 u 到起点的距离
int far_par[MAXN];      // far_par[u]：本次搜索中 u 的父节点

int dia_node[MAXN];     // 直径节点序列：左端点 -> 右端点
int dia_pos[MAXN];      // dia_pos[u]：直径节点 u 到左端点的距离
int dia_cnt;            // 直径节点个数

int dist_all[MAXN][MAXN]; // dist_all[u][v]：u 到 v 的树上距离（全源距离）

// 从 start 出发 DFS，记录每个点到 start 的距离以及父节点。
void dfs_trace(int u, int fa, int start, int d) {
    far_dis[u] = d;
    far_par[u] = fa;
    dist_all[start][u] = d;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i].v;
        int w = g[u][i].w;
        if (v == fa)
            continue;
        dfs_trace(v, u, start, d + w);
    }
}

// 返回距离 start 最远的节点，同时准备好该次搜索的距离与父节点数组。
int find_farthest(int start) {
    dfs_trace(start, 0, start, 0);
    int far = start;
    for (int u = 1; u <= n; u++) {
        if (far_dis[u] > far_dis[far])
            far = u;
    }
    return far;
}

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

    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    // 求直径：两次最远点搜索，第二次的父节点数组用于还原直径路径。
    int A = find_farthest(1);
    int B = find_farthest(A);
    // 从 B 沿着父节点一路回到 A，得到直径上的节点序列。
    for (int u = B; u != 0; u = far_par[u]) {
        dia_node[dia_cnt++] = u;
        if (u == A)
            break;
    }
    reverse(dia_node, dia_node + dia_cnt); // 现在是 A -> ... -> B 的顺序
    for (int i = 0; i < dia_cnt; i++) {
        dia_pos[dia_node[i]] = far_dis[dia_node[i]]; // 各直径节点到 A 的距离
    }

    // 以每个节点为起点做一次 DFS，得到全源距离 dist_all。
    for (int u = 1; u <= n; u++) {
        dfs_trace(u, 0, u, 0);
    }

    // 枚举所有核区间 [l, r]：直径上的连续一段，长度不超过 s。
    int ans = INT_MAX;
    for (int l = 0; l < dia_cnt; l++) {
        for (int r = l; r < dia_cnt; r++) {
            int len = dia_pos[dia_node[r]] - dia_pos[dia_node[l]];
            if (len > s)
                continue;
            // 按定义计算偏心距：所有节点到核区间的最小距离，取最大值。
            int ecc = 0;
            for (int x = 1; x <= n; x++) {
                int best = INT_MAX;
                for (int k = l; k <= r; k++) {
                    best = min(best, dist_all[x][dia_node[k]]);
                }
                if (best > ecc)
                    ecc = best;
            }
            if (ecc < ans)
                ans = ecc;
        }
    }
    cout << ans << endl;

    return 0;
}

brute.cpp 先两次最远点搜索求出直径，再对每个节点做一次 DFS 得到全源距离 $dist[u][v]$；然后枚举直径上所有长度不超过 $s$ 的核区间 $[l,r]$，对每个区间按定义计算偏心距——即对每个节点 $x$，取它到区间内各节点的距离最小值，再对这些最小值取最大。

这个暴力完全回避了偏心距的公式，直接按定义结算，是验证后续所有优化的可靠基准；但每对区间都要重扫整棵树，复杂度高达 $O(k^3 n)$（最坏 $O(n^4)$，$k$ 为直径上节点数），只适合小数据对拍。

思路

三层递进，逐步去掉重复计算：

1. 暴力层（brute.cpp）：枚举直径区间 + 按定义算偏心距，最慢但最可信。
2. 解法一（main-user.cpp）：在直径上用公式直接结算偏心距，从 $O(n^4)$ 降到 $O(n^3)$。
3. 解法二（main.cpp）：把"分支最大深度"与区间解耦，用双指针把枚举压到线性 $O(n)$，是正式主解。

两层优化都依赖两个关键性质：任取一条固定直径，只在这条直径上寻找核也不会漏掉最优解；对这条直径上的核区间 $[l,r]$，偏心距可以拆成三段：

其中 $A,B$ 是直径端点，"分支最大深度"是所有直径节点挂载的直径外子树深度的最大值，它是一个与区间选择无关的全局量。解法一每枚举一个区间就套这个公式，解法二进一步发现这个公式只依赖区间的两个端点，于是可以用双指针移动端点。

用样例 in1 的直径把三段公式落到具体数值上（核取单点 2，长度 0 不超过 $s=2$）：

1
2
3
4
5
6
7
8
9直径 A=1 → B=4，长度 9

  dist(A,l)=5               dist(r,B)=4
  ◄──────────┤                 ├──────────►
  1 ──(5)── [ 2 ] ──(4)── 4
                │
                └─ 分支深度 = 3（直径外子树最大深度）

ECC = max( 5, 4, 3 ) = 5  ← 样例答案

图中 [2] 是核：它到左端点 A 的距离是 5，到右端点 B 的距离是 4，挂载的直径外分支最大深度是 3。三者取最大得偏心距 5。可以看到，偏心距只由"核两端到直径端点的距离"和"全局分支最大深度"决定，这就是后续优化的全部依据。

公式证明

下文统一用 $d(x,y)$ 表示两个节点的树上距离，用

表示节点 $v$ 到路径 $P$ 的距离。整段证明只使用树的唯一简单路径，以及直径是全树最长路径这两个事实。

先记住三个树结构事实

后面的证明会反复用到下面三个事实：

1. 两条树上简单路径的交集仍是一条连续路径，也可能退化为一个节点。
2. 如果 $Q\cap D=[a,b]$，那么 $Q$ 离开 $D$ 的部分只能从 $a$ 或 $b$ 向外延伸。
3. 删除直径 $D$ 上的节点后，每个直径外连通块只通过一个直径节点与 $D$ 相连；否则树中会出现环。

这些事实都来自树上路径的唯一性。接下来只需处理距离关系。

先证：分支深度有界

设 $A,B$ 是直径 $D$ 的两个端点。对于不在 $D$ 上的节点 $v$，记 $u$ 为从 $v$ 沿唯一道路走到 $D$ 时第一次到达的节点，称它为 $v$ 在 $D$ 上的挂接点。要证明

这张图只展示引理中的三条关键路径：分支深度 $h=d(v,u)$，以及直径两侧的 $d(u,A)$、$d(u,B)$。

假设 $d(v,u)>d(u,A)$。从 $v$ 到 $B$ 的唯一路径必须经过 $u$，所以

这说明路径 $v\to B$ 比直径 $A\to B$ 还长，矛盾。于是 $d(v,u)\leqslant d(u,A)$。交换 $A,B$ 的位置，同理得到 $d(v,u)\leqslant d(u,B)$，引理得证。

再证：任取固定直径都不会漏解

题面规定核必须是“某条直径上的一段路径”。虽然树的直径可能不止一条，但程序用两次最远点搜索求出的只有其中一条直径 $D=[A,B]$。因此我们需要证明：任意一个满足定义的核 $Q$（可能在其它直径上），都能在这条固定的直径 $D$ 上，找到一个长度不更大、偏心距不更大的替代路径 $P$。

设 $R=\text{ECC}(Q)$。按 $Q$ 是否与 $D$ 相交分两种情况。

情况一：$Q\cap D\neq\varnothing$。

令

并按 $A\to B$ 的方向排列为 $A,\ldots,a,\ldots,b,\ldots,B$。因为 $P\subseteq Q$，所以 $P$ 的长度不超过 $s$。又因为 $Q$ 离开 $D$ 的部分只从 $a,b$ 向外延伸，所以

这张图展示相交情形的结构：红色是固定直径 $D$ 上的替代核 $P$，蓝色是可能位于另一条直径上的原核 $Q$，绿色节点是一个任意的观察节点 $v$。

对任意节点 $v$，如果 $v\in D$，令 $p=v$、$h=0$；否则令 $p$ 为 $v$ 在 $D$ 上的挂接点，$h=d(v,p)$。我们按 $p$ 的位置分类：

• $p$ 在 $a$ 的左侧。 由分支深度引理（若 $v\in D$ 则 $h=0$）有 $h\leqslant d(p,A)$，因此

  $$d(v,P)=h+d(p,a)\leqslant d(p,A)+d(p,a)=d(A,a)=d(A,Q)\leqslant R$$

• $p$ 在 $a,b$ 的内部。 此时 $p\in P\subseteq Q$。从 $v$ 到 $D$ 的唯一路径在 $p$ 处第一次到达 $Q$，所以 $d(v,Q)=h$，从而

  $$d(v,P)=h=d(v,Q)\leqslant R$$

• $p=a$。 有 $d(v,P)=h$。由引理（或 $v\in D$ 时的 $h=0$），

  $$d(v,P)=h\leqslant d(A,a)=d(A,Q)\leqslant R$$

• $p=b$。 这与 $p=a$ 的情况对称，有 $d(v,P)\leqslant d(b,B)=d(B,Q)\leqslant R$。

• $p$ 在 $b$ 的右侧。 这与 $p$ 在 $a$ 左侧的情况对称，同样得到 $d(v,P)\leqslant d(b,B)=d(B,Q)\leqslant R$。

因此所有节点到 $P$ 的距离都不超过 $R$，即

另一方面，$P\subseteq Q$，缩短路径只会让到路径的距离变大或不变，因此

两边合起来得到

情况二：$Q\cap D=\varnothing$。

删除 $D$ 上的所有节点后，$Q$ 完全位于某个直径外连通块 $C$ 中。设 $C$ 通过节点 $u\in D$ 与 $D$ 相连，取

它是 $D$ 上长度为 $0$ 的合法核。这张图展示不相交情形：原核 $Q$ 留在分支 $C$ 中，而替代核退化为固定直径上的单点 $u$。

• 如果 $v\notin C$，从 $v$ 到 $Q$ 的路径必须先经过 $u$，所以 $d(v,P)=d(v,u)\leqslant d(v,Q)\leqslant R$。
• 如果 $v\in C$，它在 $D$ 上的挂接点就是 $u$。由分支深度引理，$d(v,u)\leqslant d(A,u)$；而从 $A$ 到 $Q$ 必须经过 $u$，所以 $d(A,u)\leqslant d(A,Q)\leqslant R$。因此仍有 $d(v,P)=d(v,u)\leqslant R$。

于是 $\mathrm{ECC}(P)\leqslant\mathrm{ECC}(Q)$。这里可能是严格不等式，因为原核 $Q$ 在分支内部，替换为挂接点后可能真的降低偏心距。

综合两种情况，任意合法核都能替换成固定直径 $D$ 上的合法核，且偏心距不会变大。对一个全局最优核进行替换，就得到固定直径 $D$ 上的全局最优核。因此程序只需枚举它求出的那一条直径。

最后证：直径区间的三段公式

固定直径 $D=A\to B$ 上的核区间 $[l,r]$。对每个直径节点 $u$，定义 $h(u)$ 为从 $u$ 沿不属于 $D$ 的边进入各个直径外分支后能到达的最大距离；如果 $u$ 没有直径外节点，就定义 $h(u)=0$。记

要证明

先证上界。 记右侧最大值为

任取节点 $v$。若 $v\in D$，直径上离区间 $[l,r]$ 最远的方向只有向 $A$ 或向 $B$，所以 $d(v,[l,r])\leqslant\max(d(A,l),d(r,B))\leqslant H$。若 $v\notin D$，设 $u$ 是它在 $D$ 上的挂接点、$h_v=d(v,u)$。$v$ 到区间 $[l,r]$ 的最短路径必须经过 $u$，于是距离可以拆成"分支深度 + 挂接点到区间的距离"：

下面按 $u$ 的位置分三种情况：

• $u\in[l,r]$。 此时 $d(u,[l,r])=0$，于是

  $$d(v,[l,r])=h_v=d(v,u)$$

  也就是说：挂接点落在区间内的点，到整个核区间的距离，恰好等于它到自己的挂接点 $u$ 的距离。这一类点的距离集合，正是"区间内各挂接点 $u$ 到挂在它下面的点的距离"，最大值为 $\max_{u\in[l,r]}h(u)\leqslant M\leqslant H$。

• $u$ 在 $l$ 的左侧。 由分支深度引理 $h_v\leqslant d(u,A)$，所以

  $$d(v,[l,r])=h_v+d(u,l)\leqslant d(u,A)+d(u,l)=d(A,l)\leqslant H$$

• $u$ 在 $r$ 的右侧。 对称地有 $d(v,[l,r])\leqslant d(r,B)\leqslant H$。

所有节点到 $[l,r]$ 的距离都不超过 $H$，所以 $\mathrm{ECC}([l,r])\leqslant H$。

再证下界。 三项都能由具体节点给出：

• 节点 $A$ 到区间的距离恰为 $d(A,l)$，节点 $B$ 到区间的距离恰为 $d(r,B)$。
• 如果 $M>0$，取满足 $h(u)=M$ 的直径节点 $u$，再取其分支中满足 $d(x,u)=M$ 的节点 $x$。若 $u\in[l,r]$，则 $d(x,[l,r])=d(x,u)=M$；若 $u$ 在区间外，从 $x$ 到区间必须先经过 $u$，所以 $d(x,[l,r])\geqslant M$。如果 $M=0$，则 $\mathrm{ECC}([l,r])\geqslant0=M$ 显然成立。

因此 $\mathrm{ECC}([l,r])\geqslant H$。上下界相同，三段公式得证。

解法一：枚举直径上的所有核区间

思路

在直径上先算出每个节点到左端点 $st$ 的坐标 $pos[u]$，于是直径上任意两点距离就是坐标差，不用每次 DFS 重新求。再对每个直径节点预先求出其挂载的直径外子树最大深度 branch_depth[i]。

然后枚举所有区间 $[i,j]$：

• 若 $pos[j]-pos[i] > s$ 则跳过；
• 否则偏心距 $= \max\big(pos[i],\ diameter\_len - pos[j],\ \max_{k\in[i,j]}branch\_depth[k]\big)$，更新答案。

相比暴力，这里用"坐标差"和"三段公式"替代了按定义的全源距离结算，但区间枚举本身仍是 $O(k^2)$，每个区间还要扫一遍分支深度 $O(k)$。

代码

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/**
 * 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-08-19 09:10
 * update_at: 2026-08-19 09:10
 */
// main-user.cpp：枚举直径上所有长度不超过 s 的核区间，逐个求偏心距取最小。
// 与 main.cpp 的 O(n) 双指针不同，这里是 O(k^2) 的直白枚举（k 为直径上节点数）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;

// 链式前向星：head[u] 为 u 的第一条边编号，0 表示无边
struct Edge {
    int v, w, next;
} e[MAXN * 2];
int head[MAXN], edge_cnt;

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

int n, s;
int st, ed;          // 直径的两个端点
int dis[MAXN];       // dis[u]：u 所在子树的高度（向下最长链长度）
int from[MAXN];      // from[u]：u 的最长链从哪个子节点延续，用来还原直径
int diameter[MAXN];  // 直径上的节点，diameter[1]=st ... diameter[dia_cnt]=ed
int dia_cnt;
bool in_diam[MAXN];  // 节点是否在直径上

int pos_st[MAXN];      // pos_st[u]：直径节点 u 到 st 的距离（直径上的坐标）
int branch_depth[MAXN]; // branch_depth[i]：直径节点 diameter[i] 挂载的直径外子树最大深度

// 返回以 u 为根能到达的最远节点，并更新 dis/from
int dfs(int u, int fa) {
    dis[u] = 0;
    int far = u;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;
        int child_far = dfs(v, u);
        if (dis[v] + e[i].w > dis[u]) {
            dis[u] = dis[v] + e[i].w;
            far = child_far;
            from[u] = v;
        }
    }
    return far;
}

// 从 u 出发不经过任何直径节点，能到达的最远距离
int dfs_branch(int u, int fa) {
    int ans = 0;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == fa || in_diam[v]) continue;
        ans = max(ans, dfs_branch(v, u) + e[i].w);
    }
    return ans;
}

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

    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    // 两次最远点搜索求直径端点 st、ed
    st = dfs(1, 0);
    memset(dis, 0, sizeof(dis));
    memset(from, 0, sizeof(from));
    ed = dfs(st, 0);

    // 从 st 沿 from 一路走到 ed，得到直径上的节点序列
    for (int u = st; u; u = from[u]) {
        diameter[++dia_cnt] = u;
        in_diam[u] = true;
    }

    // 沿直径走一遍，求出每个直径节点到 st 的距离
    int cur = 0;
    for (int i = 1; i <= dia_cnt; i++) {
        pos_st[diameter[i]] = cur;
        if (i < dia_cnt) {
            for (int j = head[diameter[i]]; j; j = e[j].next) {
                if (e[j].v == diameter[i + 1]) {
                    cur += e[j].w;
                    break;
                }
            }
        }
    }
    int diameter_len = cur; // 直径长度 = st 到 ed 的距离

    // 预先把每个直径节点的分支最大深度算好
    for (int i = 1; i <= dia_cnt; i++) {
        branch_depth[i] = dfs_branch(diameter[i], 0);
    }

    int ans = INT_MAX;

    // 枚举直径上的核区间 [i,j]，要求长度不超过 s
    for (int i = 1; i <= dia_cnt; i++) {
        for (int j = i; j <= dia_cnt; j++) {
            // 直径上两点的距离 = 到 st 的距离差
            if (pos_st[diameter[j]] - pos_st[diameter[i]] > s) continue;

            // 偏心距 = max(st 到 i, j 到 ed, 区间内分支最大深度)
            int ecc = max(pos_st[diameter[i]], diameter_len - pos_st[diameter[j]]);
            for (int k = i; k <= j; k++) {
                ecc = max(ecc, branch_depth[k]);
            }
            ans = min(ans, ecc);
        }
    }

    cout << ans << endl;
    return 0;
}

复杂度

• 时间：求直径与分支深度 $O(n)$，区间枚举 $O(k^2)$、每个区间扫分支深度 $O(k)$，总 $O(n + k^3)$，最坏 $O(n^3)$。
• 空间：邻接表与直径数组，$O(n)$。

解法二：直径上双指针

思路

解法一中"每个区间扫一遍分支深度"是多余的：分支最大深度是全局量，可以在枚举前一次性算好 branch_max，与选哪段区间无关。于是偏心距公式只剩两个与区间端点相关的量：

这里的 branch_max 不是"当前区间 [l,r] 里面这些点各自能往外走多远"，而是整条直径上所有挂接分支的最大深度。也就是先对每个直径点 $u$ 计算它往直径外能走到多远，再取全局最大值 $M$；这个 $M$ 只跟整棵树有关，不跟区间 $[l,r]$ 变化，所以可以提前预处理一次。

固定左端点 $l$ 时，右端点 $r$ 在"区间长度不超过 $s$"的前提下越靠右越好——$r$ 越右，$d(r,B)$ 越小，而 $d(A,l)$ 和 $branch\_max$ 不变。因此 $r$ 只增不减，每个 $l$ 用 $O(1)$ 结算一次偏心距，枚举从 $O(k^2)$ 降到 $O(k)$。

用样例 in2（直径 $8-7-4-3-1$，长度 13，$s=6$，全局分支最大深度 4）演示双指针的完整滑动过程：

从表中看两点：第一，$r$ 只会向右移动（2 → 2 → 3 → 4 → 4），绝不会回退，这是双指针 $O(k)$ 的关键；第二，答案只在 l=2 时被更新为 5，此时区间 [4,3] 位于直径中间、两端距离最小，与"两端距离尽量小"的直觉一致。

代码

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/**
 * 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-08-12 22:28
 * update_at: 2026-08-12 22:28
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;

struct Edge {
    int v; // 邻居节点
    int w; // 边权
};

int n, s;               // n 个节点，核的长度上界 s
vector<Edge> g[MAXN];   // 邻接表存树

int far_dis[MAXN];      // far_dis[u]：本次搜索中 u 到起点的距离
int far_par[MAXN];      // far_par[u]：本次搜索中 u 的父节点，用于还原直径路径

int dia_node[MAXN];     // dia_node[i]：直径上第 i 个节点，从左端点 A 到右端点 B
int dia_pos[MAXN];      // dia_pos[u]：直径节点 u 到左端点 A 的距离（即直径上的坐标）
int dia_cnt;            // 直径上的节点个数
bool on_dia[MAXN];      // on_dia[u]：节点 u 是否在直径上

int branch_max;         // 所有直径节点挂载的直径外子树的最大深度

// 从 start 出发 DFS 遍历整棵树，记录距离与父节点。
void dfs_dist(int u, int fa, int d) {
    far_dis[u] = d;
    far_par[u] = fa;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i].v;
        int w = g[u][i].w;
        if (v == fa)
            continue;
        dfs_dist(v, u, d + w);
    }
}

// 返回距离 start 最远的节点，并让 far_dis/far_par 记录本次搜索结果。
int find_farthest(int start) {
    dfs_dist(start, 0, 0);
    int far = start;
    for (int u = 1; u <= n; u++) {
        if (far_dis[u] > far_dis[far])
            far = u;
    }
    return far;
}

// 两次最远点搜索求出直径 A-B，并把直径路径与坐标存好。
void get_diameter() {
    int A = find_farthest(1);
    int B = find_farthest(A);
    // 从 B 沿着父节点一路回到 A，得到直径上的节点序列。
    for (int u = B; u != 0; u = far_par[u]) {
        dia_node[dia_cnt++] = u;
        if (u == A)
            break;
    }
    reverse(dia_node, dia_node + dia_cnt); // 现在是 A -> ... -> B 的顺序
    for (int i = 0; i < dia_cnt; i++) {
        int u = dia_node[i];
        on_dia[u] = true;
        dia_pos[u] = far_dis[u]; // 第二次搜索的距离数组正是各点到 A 的距离
    }
}

// 统计直径节点 u 挂载的直径外子树的最大深度，用 best 带回。
void dfs_branch(int u, int fa, int d, int& best) {
    if (d > best)
        best = d;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i].v;
        int w = g[u][i].w;
        if (v == fa || on_dia[v])
            continue;
        dfs_branch(v, u, d + w, best);
    }
}

// 对每个直径节点求其直径外子树深度，取全局最大值。
void compute_branch_max() {
    for (int i = 0; i < dia_cnt; i++) {
        int best = 0;
        dfs_branch(dia_node[i], 0, 0, best);
        if (best > branch_max)
            branch_max = best;
    }
}

void solve() {
    int diameter_len = dia_pos[dia_node[dia_cnt - 1]]; // 直径长度 = B 到 A 的距离
    int ans = diameter_len;                            // 偏心距不可能超过直径长度
    int r = 0;
    for (int l = 0; l < dia_cnt; l++) {
        if (r < l)
            r = l;
        // 固定左端点 l，右端点 r 尽量右移，保持区间长度不超过 s。
        while (r + 1 < dia_cnt &&
               dia_pos[dia_node[r + 1]] - dia_pos[dia_node[l]] <= s) {
            r++;
        }
        // 偏心距 = max(A 到左端点, 右端点到 B, 直径外子树最大深度)
        int left_dist = dia_pos[dia_node[l]];
        int right_dist = diameter_len - dia_pos[dia_node[r]];
        int ecc = max(max(left_dist, right_dist), branch_max);
        if (ecc < ans)
            ans = ecc;
    }
    cout << ans << endl;
}

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

    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    get_diameter();
    compute_branch_max();
    solve();

    return 0;
}

复杂度

• 时间：两次最远点搜索求直径 $O(n)$、分支最大深度 $O(n)$、双指针 $O(k)$，总 $O(n)$。
• 空间：邻接表与直径数组，$O(n)$。

复杂度对比

三者的差异只在"偏心距怎么算、区间怎么枚举"：暴力按定义算，解法一用公式但枚举不减，解法二让枚举随端点滑动。

总结

树网的核是"先降到直径，再在直径上做约束枚举"的经典模型。核心洞察是把偏心距拆成三段，其中分支最大深度与区间选择无关，于是问题退化成在直径上找"两端距离尽量小、长度不超过 $s$"的区间——一个典型的两端约束，双指针天然适用。解法一用直白的枚举验证公式，解法二用双指针逼近线性，两条路径共用同一套直径求法。

图示解析

这张 ASCII 图展示整道题的解题路线：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  枚举直径上所有长度不超过 s 的核区间
  对每个区间按定义 BFS/全源距离算偏心距      O(k^3 n)
        |
        | 瓶颈：每个区间都要重新算整棵树到核的最大距离
        v
关键性质
  任取一条固定直径 D，只在 D 上寻找也不会漏掉最优核
  对直径上的核 [l, r]：
    偏心距 = max( A 到 l 的距离, r 到 B 的距离, 直径外所有分支的最大深度 )
  分支最大深度是全局量，与选哪段无关
        |
        v
解法一（main-user.cpp）：枚举直径区间套公式          O(k^3)
        |
        | 改进：分支深度与区间无关，公式只依赖端点
        v
解法二（main.cpp）：左端点固定时右端点单调右移        O(n)

观察要点：三条主线对应"暴力慢在哪"“直径上的核如何把偏心距拆成三段”“为什么 $r$ 可以只往右走”。核心是分支最大深度与区间选择无关，所以双指针每次移动都只用两端距离做比较。

另一视角：Gemini 的证明

上面的证明从"挂接点 + 交并分情况"出发；Gemini 给出了另一套讲法——多直径"相交且对称"的视角，两个版本互相印证，适合对照阅读：

来源：Gemini 对话导出（2026-08-19），仅保留证明部分。

引理：分支深度有界

结论： 设 $A,B$ 是直径 $D$ 的端点，$v$ 是不在直径上的任意节点，$u$ 是 $v$ 连入直径的"挂接点"（即 $v$ 到 $D$ 上距离最近的点）。则：

证明（反证法）： 要证明 $d(v,u)$ 同时小于等于 $d(u,A)$ 和 $d(u,B)$。

1. 假设结论不成立：不妨假设 $d(v,u) > d(u,A)$。
2. 寻找矛盾：在树中，从节点 $v$ 走到节点 $B$ 的唯一路径，必然是先从 $v$ 走到挂接点 $u$，然后再从 $u$ 走到 $B$。因此这条路径的长度为：

3. 根据假设 $d(v,u) > d(u,A)$ 代入上式：

4. 而 $u$ 是直径 $A-B$ 上的点，所以 $d(u,A) + d(u,B) = d(A,B)$，即：

5. 得出结论：找到了一条路径 $v \to B$，长度大于直径 $A \to B$，与"直径是树中最长路径"的定义矛盾。

同理，假设 $d(v,u) > d(u,B)$ 会得出 $d(v,A) > d(A,B)$ 的矛盾。证毕。

教练注：直径就像树的"主干道"，任何一条"岔路"的长度，绝对不可能比它所连接的主干道两端还要长，否则这条岔路早就篡位变成新的主干道了。

结论：在任意一条直径上找核，都不会漏掉最优解

结论： 如果树有过多条直径，任取其中一条固定直径 $D$ 进行搜索，得到的最小偏心距一定等于全局的最优（最小）偏心距。

证明： 只需要弄清楚当树有多条直径时，它们长什么样。

第一步：多条直径的结构性质（相交且对称）

在树中，任意两条直径必定相交（共享一段连续的路径）。设两条直径 $D_1$（端点 $A_1, B_1$）和 $D_2$（端点 $A_2, B_2$），它们必定在树的中央有一段重合的路径，设重合部分为 $X \dots Y$。既然 $D_1$ 和 $D_2$ 都是最长路径，它们没有重合的"分叉"部分长度必然完全相等：

（若 $d(A_2, X) > d(A_1, X)$，那 $A_1-B_1$ 就不配叫直径了。）

第二步：分析偏心距的构成

不管选哪条直径（假设选了 $D_1$），在这个直径上取一段不超过长度 $s$ 的路径作为核 $F$。这个核 $F$ 的偏心距 $\mathrm{ECC}(F)$ 只可能来自三个方向：

1. $F$ 到左端点 $A_1$ 的距离；
2. $F$ 到右端点 $B_1$ 的距离；
3. $F$ 到某条"岔路"底部的距离（比如到另一条直径的端点 $A_2$）。

第三步：为什么换一条直径结果一样

假设在 $D_1$ 上找到了一个最优的核 $F$。

• 情况 A（$F$ 在重合区域 $X \dots Y$ 内）：从 $F$ 走到 $A_1$ 必须经过 $X$，从 $F$ 走到 $A_2$ 也必须经过 $X$。因为 $d(A_1, X) = d(A_2, X)$，所以 $F$ 到 $A_1$ 和到 $A_2$ 的距离完全相等。对于 $F$ 来说，无论你管 $A_1$ 叫"直径的端点"还是管 $A_2$ 叫"岔路的端点"，距离的最大值根本没有改变，把 $F$ 放在 $D_2$ 上看，偏心距数值一模一样。

• 情况 B（$F$ 偏离了重合区域，比如伸进了 $X \to A_1$ 分叉）：如果核 $F$ 往 $A_1$ 的方向挪动，它离 $A_1$ 是近了，但它离 $A_2$ 的距离却变成了 $d(F, X) + d(X, A_2)$，这反而会拉大 $F$ 到 $A_2$ 的距离，导致偏心距变大（变劣）。在对称的分叉结构中，核 $F$ 无论往哪个分叉里钻，都会受到另一个等长分叉的制约；换做在 $D_2$ 的 $X \to A_2$ 分叉上找核，面临的距离约束在数学上是完全同构的。

总结论： 其他直径的存在，无非是在原本的直径上接了几条长度完全相等的岔路。因为它们的长度对称，不论你以哪条为主干道，计算出的各个极值距离必然是完全相同的。因此，任取一条直径作为参考系，就足以覆盖整棵树的极限约束，绝对不会漏掉最优解。证毕。

进阶思考：如果题目不限制核必须在直径上呢

假设题目只问：“在无根树中，任选一条长度不超过 $s$ 的路径 $F$，要求其偏心距最小”，那这个最优解 $F$ 还会在直径上吗？

答案是必然的。即使题目不强制要求，最优的路径也一定会贴合在直径上：

1. 树的偏心距由"极值点"决定：一棵树里距离最远的两个点，就是直径的端点（设为 $A$ 和 $B$）。任何路径 $F$ 的偏心距，绝大多数情况下是由 $F$ 到 $A$ 或 $F$ 到 $B$ 的距离决定的。

2. 树的中心吸引力：树的绝对中心（到所有叶子节点最大距离最小的点）必然在直径的中点。如果路径 $F$ 远离了树的中心，完全偏离了直径（比如跑到了某条边缘的岔路上），那么它距离直径的某一端（$A$ 或 $B$）就会变得非常遥远——因为去往 $A$ 或 $B$ 的路必须先退回直径，这会平白无故增加一大段距离，导致偏心距暴增。

3. 投影收敛（反证法）：假设有一条不在直径上的最优路径 $F'$。将 $F'$ 顺着树枝向直径的方向"投影"或平移，使其靠近直径。在这个靠近的过程中：

   • 它距离原先最远的端点（$A$ 或 $B$）的距离会缩小；
   • 它距离其他侧边分支的距离虽然会变化，但有"分支深度有界"引理兜底：侧分支的深度永远不可能超过主干道端点的距离；
   • 因此，将路径强行推到直径上，偏心距只可能变小，绝不可能变大。

这就是为什么在处理树上路径最值问题时，"直径"和"树的中心"是所有最长距离的万物之源。

最终公式

固定直径 $D=A\to B$ 上的核区间 $[l,r]$。对每个直径节点 $u$，定义 $h(u)$ 为从 $u$ 沿不属于 $D$ 的边进入各个直径外分支后能到达的最大距离；如果 $u$ 没有直径外节点，就定义 $h(u)=0$。记

要证明

最后一个公式 是否正确, 如何证明 ?

这个公式完全正确！它不仅是正确的，而且是极其优美的数学表达。

从算法的角度看，正是这个公式将这道题的复杂度从暴力的 $O(n^3)$ 直接降维打击到了线性的 $O(n)$。我们可以用离散数学中集合划分 (Partition) 的思想，配合刚才提到的“引理”，给出一个非常清晰、低心智负担的证明。

核心证明过程

我们要计算核区间 $[l,r]$ 的偏心距 $\mathrm{ECC}([l,r])$，本质上就是要找全树所有节点到区间 $[l,r]$ 的最大距离。

根据树的结构，我们根据任意节点 $v$ 在直径 $D$ 上的挂接点 $u$ 的位置，将全树的所有节点划分为三个互不相交的集合：

集合 1：挂接点 $u$ 在区间左侧 ($A \to l$ 路径上，不含 $l$)

对于这个集合里的任意节点 $v$，它要走到核 $[l,r]$，最近的入口必然是端点 $l$。 所以它到核的距离是：$d(v,u) + d(u,l)$。 根据我们的引理，$d(v,u) \leqslant d(u,A)$。 将不等式代入，得到：

由于直径的端点 $A$ 本身也在这个集合里，且 $A$ 到 $l$ 的距离刚好就是 $d(A,l)$。 结论 1：集合 1 中所有点到核的最大距离，精准等于 $d(A,l)$。

集合 2：挂接点 $u$ 在区间右侧 ($r \to B$ 路径上，不含 $r$)

完全同理，利用对称性可知，对于该集合中的任意节点 $v$，它走到核的最近入口是 $r$。 根据引理 $d(v,u) \leqslant d(u,B)$，有：

结论 2：集合 2 中所有点到核的最大距离，精准等于 $d(r,B)$。

集合 3：挂接点 $u$ 在核区间内 ($u \in [l,r]$)

对于这个集合里的节点 $v$，它的挂接点 $u$ 本身就在核内！所以 $v$ 到核的距离就是它到挂接点的距离 $d(v,u)$。 而 $h(u)$ 的定义就是挂接点 $u$ 往外延伸的最大深度。 结论 3：集合 3 中所有点到核的最大距离，精准等于 $\max_{u \in [l,r]} h(u)$。

汇总与“吸收律”的魔法

综合以上三个集合，我们可以得到一个“严格版”的公式：

为什么公式里可以把局部的 $\max_{u \in [l,r]} h(u)$ 替换成全局的 $M$ 呢？ 这就是这个公式最巧妙的逻辑跃迁： 假设有一个点 $u$ 在核的外侧（比如在 $A \to l$ 这一段），它的 $h(u)$ 会有多大？ 根据引理，$h(u) \leqslant d(A,u)$。 显然，$d(A,u) \leqslant d(A,l)$。 也就是说，核外侧的所有 $h(u)$，天然被 $d(A,l)$ 或 $d(r,B)$ 压制（Dominate）了！

全局直径上的最大侧枝深度 $M$ 实际上可以被写成三个子集的并集的极值：

直接用我们推导出的“严格版”偏心距公式：

现在，我们将 $\max_{x \in A \to l} h(x),\ \max_{y \in r \to B} h(y)$ 强行塞进这个 $\max$ 函数里，得到一个 5 项公式：

为什么塞进去不影响结果？（吸收律的本质） 因为根据我们最开始证明的引理（分支深度有界）：

1. 对于左侧外部的任意点 $x$，$h(x) \leqslant d(A,x) < d(A,l)$，所以 $\max_{x \in A \to l} h(x)$ 永远被 $d(A,l)$ 压制。
2. 同理，$\max_{y \in r \to B} h(y)$ 永远被 $d(r,B)$ 压制。

在求最大值的运算中，加入比已知最大值小的项，不改变最终结果。 所以你的这步操作在数学上叫做恒等变换。

而当你把这 5 项摆在一起时，奇迹就发生了：后面这 3 个 $h$ 相关的项，刚好拼凑成了全局的 $M$！ 于是公式顺理成章地折叠成了最简形式：

你的这种推导方式，在离散数学和算法证明中被称为“放缩与吸收” (Relaxation and Absorption)。你非常漂亮地完成了这一跃迁。

既然外面的 $h(u)$ 绝对不可能超过 $d(A,l)$ 和 $d(r,B)$，那我们把它们一股脑全部塞进 $\max$ 函数里，完全不会影响最终的最大值结果。 于是，局部极值被优雅地扩张成了全局不变量：

证毕。