带权树每个子树求偏心距最小的点的偏心距,即子树半径,用树形 DP 与长链剖分求中点。
OJ: roj
题目 ID: 1758
难度:提高+/省选-
标签:树形DP长链剖分二分数据结构
创建: 2026-10-07 22:30
更新: 2026-10-07 22:30
形式化题目
给定一棵
对任意结点集合
对每个结点
正解
思路
一个子树的能力就是它的半径:对任意树,若
沿
设子树
- 完全落在某个孩子的子树内部,即
; - 经过
本身,即 ,其中 是 向下最长的两条臂(向下最长链)的长度,且它们来自不同孩子。
于是:
- 情况 1:直径两端都在孩子
的子树里, – 路径上的点集与子树 内的完全一致,故 。 - 情况 2:直径端点是
( 那条臂的端点)与 ( 那条臂的端点),路径 经过 ;最优点在 这一段上( 保证 那侧不会更优)。条件 用 的深度表达成 ,是一个随深度单调的判定,可以在 这条链上二分。
关键观察:lower_bound,总复杂度
| 数组 | 含义 |
|---|---|
| 最长臂所在的孩子,即长链剖分的"重孩子" | |
| 子树 |
|
| 直径继承自哪个孩子;为 |
|
| 子树 |
样例
代码
C++17 版本使用链式前向星、迭代 BFS(避免 long long(最远可达 int 会溢出)。
/**
* 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-07 22:30
* update_at: 2026-10-07 22:30
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* 一本通 1758《连通能力》
* 每个点 i 的答案 = 以 i 为根的子树(i 的全部后代)的半径
* = min_{v 在子树 i 内} ( v 到子树内其它点的最大距离 )
* 做法:树形 DP 求子树直径,再用“长链剖分 + 二分”在直径路径上找最优点。
* - 子树直径 D 只有两种来源:某个孩子的子树内部,或者经过 i 的两条最长臂之和。
* - 若 D 来自孩子 c,则答案就等于 ans[c](直径两端都在 c 的子树里,
* 而子树半径只会被直径两端决定)。
* - 否则直径端点就是 i 的两条最长臂端点,最优点落在 p1[i] 到 i 的这条链上;
* 而 p1[i] 正是 i 所在长链的链底,于是“向上跳到中点”变成在长链上二分。
* 复杂度 O(N log N)(二分是 std::lower_bound 的 O(log N)),数组全部 O(N)。
*/
const int MAXN = 1000005; /* N 上限 1e6,开 1e6+5 */
int n;
/* ---------- 链式前向星存树 ---------- */
int head[MAXN]; // head[u]:u 的第一条边
int nxt[2 * MAXN]; // 下一条边的编号
int to[2 * MAXN]; // 边的另一个端点
int wt[2 * MAXN]; // 边权
int ecnt; // 已加入的边数(双向,2*(N-1) 条)
int fa[MAXN]; // fa[v]:以 1 为根时 v 的父亲,根的父亲为 0
int parw[MAXN]; // parw[v]:v 到父亲那条边的边权
int order[MAXN]; // BFS 序:父亲一定排在孩子前面,逆序即自底向上
ll dis[MAXN]; // dis[v]:v 到根 1 的距离
ll f1[MAXN]; // f1[v]:v 的子树内从 v 向下走的最长臂长
ll f2[MAXN]; // f2[v]:次长臂长(与最长臂来自不同孩子,无则为 0)
int hc[MAXN]; // hc[v]:最长臂所在的孩子(长链剖分的“重孩子”),叶子为 0
ll dia[MAXN]; // dia[v]:子树 v 的直径
ll ans[MAXN]; // ans[v]:子树 v 的半径 = 本题答案
int best_child[MAXN]; // 直径最大的孩子;为 0 表示直径的两条臂都在 v 身上(要重算)
/* ---------- 长链:把每条重链从上到下展开在 chain_dis 里 ---------- */
int pos[MAXN]; // pos[v]:v 在 chain_dis 中的下标
int chend[MAXN]; // chend[v]:v 所在长链的链底在 chain_dis 中的下标
ll chain_dis[MAXN]; // 同一条长链上 dis 严格递增,便于二分
/* ---------------- 快读 ---------------- */
static char ibuf[1 << 20];
static int ilen = 0, ipos = 0;
static inline int gc() {
if (ipos == ilen) {
ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin);
ipos = 0;
if (ilen <= 0) return -1;
}
return (unsigned char)ibuf[ipos++];
}
static inline int read_int() {
int c = gc();
while (c != -1 && (c < '0' || c > '9')) c = gc();
if (c == -1) return -1;
int x = 0;
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
return x;
}
/* ---------------- 快写 ---------------- */
static char obuf[1 << 22];
static int olen = 0;
static inline void o_flush() {
if (olen) { fwrite(obuf, 1, olen, stdout); olen = 0; }
}
static inline void o_putc(char c) {
if (olen == (int)sizeof(obuf)) o_flush();
obuf[olen++] = c;
}
static inline void o_putll(ll x) {
char t[24];
int k = 0;
if (x == 0) t[k++] = '0';
while (x > 0) { t[k++] = (char)('0' + (int)(x % 10)); x /= 10; }
while (k > 0) o_putc(t[--k]);
}
static inline void add_edge(int u, int v, int w) {
++ecnt; to[ecnt] = v; wt[ecnt] = w; nxt[ecnt] = head[u]; head[u] = ecnt;
++ecnt; to[ecnt] = u; wt[ecnt] = w; nxt[ecnt] = head[v]; head[v] = ecnt;
}
/* 从根 1 出发 BFS 定根:得到 fa、parw、dis 和自底向上要用的 order */
void bfs_root() {
int qt = 0;
order[qt++] = 1;
fa[1] = 0;
parw[1] = 0;
dis[1] = 0;
for (int qh = 0; qh < qt; ++qh) {
int u = order[qh];
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if (v == fa[u]) continue; /* 树上无重边,跳过父亲即不回头 */
fa[v] = u;
parw[v] = wt[e];
dis[v] = dis[u] + wt[e];
order[qt++] = v;
}
}
}
/* 第一遍自底向上:把每个点的 f1、f2、hc 和直径信息推给父亲
* (逆向 BFS 序保证处理 v 时它的所有孩子都已把信息推上来) */
void dp_diameter() {
for (int idx = n - 1; idx >= 0; --idx) {
int u = order[idx];
ll through = f1[u] + f2[u]; /* 经过 u 的最长路径(= 两条最长臂之和) */
if (through >= dia[u]) {
dia[u] = through; /* 直径经过 u 本身,要把最优中心重新算 */
best_child[u] = 0;
}
if (u == 1) continue;
int p = fa[u];
ll val = f1[u] + parw[u]; /* u 这条臂延伸到 p 之后的长度 */
if (val > f1[p]) {
f2[p] = f1[p];
f1[p] = val;
hc[p] = u; /* 最长臂来自 u,u 是 p 的重孩子 */
} else if (val > f2[p]) {
f2[p] = val;
}
if (dia[u] > dia[p]) {
dia[p] = dia[u]; /* p 的直径可以由孩子 u 继承 */
best_child[p] = u;
}
}
}
/* 长链剖分:每个点沿 hc 一路向下就是它的长链,链上 dis 单调递增 */
void build_chains() {
int ptr = 0;
for (int i = 0; i < n; ++i) {
int u = order[i];
if (u != 1 && hc[fa[u]] == u) continue; /* 不是链顶,已经随链顶展开过 */
for (int v = u; v != 0; v = hc[v]) {
pos[v] = ptr;
chain_dis[ptr] = dis[v];
++ptr;
}
int last = ptr - 1;
for (int v = u; v != 0; v = hc[v]) chend[v] = last;
}
}
/* 第二遍自底向上:算答案 */
void dp_answer() {
for (int idx = n - 1; idx >= 0; --idx) {
int u = order[idx];
if (best_child[u] != 0) {
ans[u] = ans[best_child[u]]; /* 直径整段落在孩子子树里,半径相同 */
continue;
}
/* 直径端点是 p1[u](长链链底)和 p2[u],最优点在这条路径上,
* 且在 p1[u] 到 u 这一段:找满足 2*d(p1,x) <= D 的最高点 x,
* 答案取 x 与其父亲两个候选的较小值。
* 注意 dis[p1[u]] = dis[u] + f1[u]。 */
ll D = dia[u];
ll t = 2 * (dis[u] + f1[u]) - D; /* 判定条件等价于 2*dis[x] >= t */
ll need = (t + 1) / 2; /* ceil(t/2),t 恒 >= 0 */
int lo = pos[u];
int hi = chend[u];
int p = (int)(lower_bound(chain_dis + lo, chain_dis + hi + 1, need) - chain_dis);
ll best = f2[u] + (chain_dis[p] - dis[u]); /* max(d(x,p1), d(x,p2)) = d(x,p2) */
if (p > lo) {
ll alt = f1[u] - (chain_dis[p - 1] - dis[u]); /* 上面一个点:max = d(p1,x') */
if (alt < best) best = alt;
}
ans[u] = best;
}
}
int main() {
n = read_int();
if (n <= 0) n = 1;
for (int i = 1; i < n; ++i) {
int u = read_int(), v = read_int(), w = read_int();
add_edge(u, v, w);
}
bfs_root();
dp_diameter();
build_chains();
dp_answer();
for (int i = 1; i <= n; ++i) {
o_putll(ans[i]);
o_putc('\n');
}
o_flush();
return 0;
}Python 版本沿用同一算法与同一长链剖分二分,用 array 存稠密数组以把内存在常数上压下来。
#!/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-07 22:30
# update_at: 2026-10-07 22:30
import sys
from array import array
from bisect import bisect_left
from collections.abc import Iterator
CHUNK = 4096 # 输出每次写多少行:1e6 行一次性 join 会多占几十 MB
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type DataIter = Iterator[int] # 顺序消费的整数流
type Graph = tuple[array, array, array, array] # (head, nxt, to, wt) 链式前向星
type Rooted = tuple[array, array, array, array] # (fa, parw, dis, order) 自根向下的信息
type Arms = tuple[array, array, array, array, array] # (f1, f2, hc, dia, src) 树形 DP 结果
type Chains = tuple[array, array, array] # (pos, chend, chain_dis) 长链剖分展开
def build_graph(n: int, data: DataIter) -> Graph:
"""把 n-1 条边读成链式前向星,边 e 与 e+1(e 为偶数)互为反向边。"""
head = array('i', bytes(4 * (n + 1))) # head[u]:u 的第一条边,0 表示没有
nxt = array('i', bytes(8 * n)) # 下一条边,编号最大 2n-1
to = array('i', bytes(8 * n)) # 边的另一个端点
wt = array('i', bytes(8 * n)) # 边权
for e in range(2, 2 * n, 2):
u, v, w = next(data), next(data), next(data)
to[e], wt[e], nxt[e], head[u] = v, w, head[u], e
to[e + 1], wt[e + 1], nxt[e + 1], head[v] = u, w, head[v], e + 1
return head, nxt, to, wt
def rooted(n: int, graph: Graph) -> Rooted:
"""以 1 为根做迭代 BFS:父亲 fa、父边权 parw、到根距离 dis、BFS 序 order。"""
head, nxt, to, wt = graph
fa = array('i', bytes(4 * (n + 1)))
parw = array('i', bytes(4 * (n + 1)))
dis = array('q', bytes(8 * (n + 1))) # 距离最大 1e6*1e4=1e10,必须 64 位
order = array('i', bytes(4 * (n + 1)))
order[0] = 1
qt = 1
for qh in range(n):
u = order[qh]
du, pu, e = dis[u], fa[u], head[u]
while e:
v = to[e]
if v != pu: # 树上无重边,不回走父亲即不重复访问
fa[v], parw[v], dis[v], order[qt] = u, wt[e], du + wt[e], v
qt += 1
e = nxt[e]
return fa, parw, dis, order
def arms(n: int, fa: array, parw: array, dis: array, order: array) -> Arms:
"""逆 BFS 序(即自底向上)求每个子树的 f1、f2、重孩子 hc、直径 dia、来源 src。
src[u] = 直径继承自哪个孩子;为 0 表示直径经过 u 本身,最优点需要在链上重找。
"""
f1 = array('q', bytes(8 * (n + 1))) # f1[u]:u 向下最长臂长
f2 = array('q', bytes(8 * (n + 1))) # f2[u]:次长臂长(来自另一个孩子,无则 0)
hc = array('i', bytes(4 * (n + 1))) # hc[u]:最长臂所在的孩子,即长链的重孩子
dia = array('q', bytes(8 * (n + 1))) # dia[u]:子树 u 的直径
src = array('i', bytes(4 * (n + 1))) # 直径来源孩子,0 表示要重算答案
for k in range(n - 1, -1, -1):
u = order[k]
through = f1[u] + f2[u] # 经过 u 本身的最长路径
if through >= dia[u]:
dia[u] = through
src[u] = 0
if u == 1:
continue
par = fa[u]
val = f1[u] + parw[u] # u 这条臂延伸到父亲之后的长度
if val > f1[par]:
f2[par], f1[par], hc[par] = f1[par], val, u
elif val > f2[par]:
f2[par] = val
if dia[u] > dia[par]:
dia[par], src[par] = dia[u], u
return f1, f2, hc, dia, src
def chains(n: int, order: array, fa: array, hc: array, dis: array) -> Chains:
"""长链剖分:每条链自上而下展开,链上 dis 严格递增,可以直接二分。"""
pos = array('i', bytes(4 * (n + 1))) # pos[u]:u 在 chain_dis 里的下标
chend = array('i', bytes(4 * (n + 1))) # chend[u]:u 所在链的链底下标
chain_dis = array('q', bytes(8 * (n + 1)))
ptr = 0
for k in range(n):
u = order[k]
if u != 1 and hc[fa[u]] == u:
continue # 不是链顶,已随链顶一起展开过
v = u
while v:
pos[v], chain_dis[ptr] = ptr, dis[v]
ptr += 1
v = hc[v]
last = ptr - 1
v = u
while v:
chend[v] = last
v = hc[v]
return pos, chend, chain_dis
def answers(n: int, order: array, dis: array, arm: Arms, chain: Chains) -> array:
"""逆 BFS 序求每个子树的能力(半径)。
直径来自孩子时半径直接继承;直径经过 u 时,两条最长臂端点 p1(链底)、p2
确定唯一一条直径,最优点就在 p1 到 u 这一段上,用二分找满足
2*d(p1,x) >= D 的最低点 x,取 x 与其上一个点的较小值。
"""
f1, f2, _hc, dia, src = arm # _hc 只在 chains() 里用到
pos, chend, chain_dis = chain
ans = array('q', bytes(8 * (n + 1)))
for k in range(n - 1, -1, -1):
u = order[k]
c = src[u]
if c:
ans[u] = ans[c] # 直径整段落在孩子子树里,半径相同
continue
need = (2 * (dis[u] + f1[u]) - dia[u] + 1) // 2 # 条件 2*dis[x] >= t 的阈值
lo, hi = pos[u], chend[u]
q = bisect_left(chain_dis, need, lo, hi + 1)
best = f2[u] + chain_dis[q] - dis[u] # d(x,p2) 是这一侧的最大值
if q > lo:
alt = f1[u] - chain_dis[q - 1] + dis[u] # 上一个点由 d(p1,·) 决定
if alt < best:
best = alt
ans[u] = best
return ans
def solve() -> None:
# 按行边读边产出整数:改成 sys.stdin.buffer.read().split() 会把 3e6 个 token
# 同时物化成列表,N=1e6 时白占约 100MB(实测 142MB -> 250MB),逼近 256MB 限制。
data: DataIter = (int(x) for line in sys.stdin.buffer for x in line.split())
n = next(data)
graph = build_graph(n, data)
fa, parw, dis, order = rooted(n, graph)
arm = arms(n, fa, parw, dis, order)
heavy_child = arm[2] # hc:长链剖分要用的重孩子数组
chain = chains(n, order, fa, heavy_child, dis)
ans = answers(n, order, dis, arm, chain)
out = sys.stdout
for start in range(1, n + 1, CHUNK): # 分块写出,避免 1e6 行一次性 join
out.write('\n'.join(map(str, ans[start:start + CHUNK])))
out.write('\n')
if __name__ == "__main__":
solve()复杂度
时间 lower_bound,长度总和为
总结
- 子树能力 = 子树半径,半径由直径决定:
。 - 子树直径的两种来源对应两条转移:来自孩子则直接继承答案,经过自己则只需在"自己的最长臂"这条链上找中点。
- 用长链剖分把"沿祖先上跳"变成数组二分,省掉倍增表与
层的存储开销;迭代 BFS 逆序 DP 保证 的链不会爆栈。
关于数据来源:本题素材源目录里带有 data.py(自建数据生成器)与 std.cpp,说明 data/ 不是官方原始数据,题面也可能是按经典题重建的,出题意图与官方原题可能存在偏差。本解已先编译 std.cpp 并在 data/ 上逐点与 .out 比对(10/10 一致),且对 std.cpp。与 std.cpp 相比,本解把"沿祖先倍增上跳"换成了长链剖分上的二分,并去掉了