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

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

1000ms

Difficulty: 8

所属公司 : 携程

算法与标签>二分算法

题目内容

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

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

求该最小的 $D$ 。

【名词解释】

第一行输入两个整数 $n,m(2≦m≦n≦2×10^5)$ ，分别表示节点数和红点数。

第二行输入 $m$ 个且不相同的整数 $r_1,r_2,…,r_m(1≦r_1≦n)$ 。表示红点节点的编号。

接下来 $n-1$ 行，每行输入三个整数 $u_i,v_i,w_i(1≦u_i,v_i≦n,u_i≠v_i,1≦w_i≦10^5)$ ，表示一条无向带权边。

保证输入构成一颗树。

输出一个整数 $D$ ，表示选择恰好 $2$ 个节点作为中心时，所有红点到最近中心的最大带权距离。

输入

输出

说明

可选择节点 $3$ 和 $6$ 作为中心。

输入

预期输出（选填）