Skip to content

1057: Pio's Hometown

题目

题目描述

Pio 是一名药水制作师,制作药水需要许多种类的素材,而 Pio 每天会到小镇上 $k$ 个不同的店铺采购这些素材。Pio 所居住的小镇位于王国边缘,我们可以将其看成一棵有 $n$ 个结点的树,任意一条树边 $e_i$ 的长度为 $l_i$ 。

你知道聪明的 Pio 为了节约每天在路上花费的时间,把药水店开在了使 距离最远的店铺最近 的结点上。作为守护这个小镇、即将出发讨伐恶龙的勇者,你想要到 Pio 的药水店买些生命药水。你能在小镇上找到 Pio 的药水店吗?

输入格式

第一行是两个正整数 $n, k$

对于接下来的 $n-1$ 行,第 $i$ 行输入三个非负整数 $u_i, v_i, l_i$ ,表示结点 $u_i$ 与 $v_i$ 之间有一条长度为 $l_i$ 的树边,结点编号从 $0$ 开始

第 $n+1$ 行是 $k$ 个非负整数,分别表示 $k$ 个店铺所在的结点编号

输出格式

共一行,用空格分隔,输出 Pio 的药水店所在的结点编号以及 Pio 的药水店到最远的店铺之间的距离

  • 如果有多个药水店可能所在的结点,请输出编号最小的结点

样例输入

text 5 2 0 3 733 3 2 923 1 3 662 1 4 452 0 1

样例输出

text 3 733

数据范围

$1\leq n\leq 10^5$, $2\leq k\leq10$, $0<l_i\leq10^3$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!