会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（携程机考编程题库），可解锁完整内容。

购买题库开通会员

核心化树（Steiner Tree）：只保留连接所有红点所必需的节点与边（反复删除非红点的叶子）。
直径路径：在该核心树上求红点间的加权直径端点 $a,b$ ，得到路径 $P$ 。最优的两个中心可以假设都在 $P$ 上。
投影与权重：每个红点都“投影”到 $P$ 的某个结点 $p$ ，其到 $p$ 的距离为“垂距” $h$ 。同一个 $p$ 可能有多个红点投影，记 $H(p)=\max h$ 。仅保留那些 $H(p)$ 定义存在的 $p$ （即 $p$ 自身是红点或有侧枝红点）。
转为路径上的带权两中心：若在 $P$ 上放两个中心 $x,y$ ，则对任意保留的路径结点 $p$ ，要求

题目内容

给定一棵包含 $n$ 个节点的无向连通树，每条边 $(u,v)$ 的权重为正整数 $w_uv$ 。树上有 $m$ 个被标记为"红点"的节点。

现在需要在树中选择恰好 $2$ 个节点作为中心，使得所有红点到最近中心的最大带权距离 $D$ 最小。

求该最小的 $D$ 。

请从“运行结果”或“历史提交”选择一条记录

选择提交后开始分析

#P3600. 第4题-最大带权距离