破译信号

循环的旁边是一棵树——不是普通的树，是一棵只有一根树枝弯回来、和自己连在一起的树。Echo说，这叫"基环树"，是树和循环的混血儿。

"Zero的传呼系统。"她说，"每个节点是一个基站，信号沿着树枝传递。但有一个基站，它的信号会传回自己——形成了一个环。"

"我们要做啥子？"CC问。

"找到那个环上的关键节点。"你说，"如果信号要覆盖所有基站，最优的中转站在哪？"

"这就像……"CC想了想，"像找邮局。要选一个位置，让所有人去寄信都方便。"

"对。"

你开始写。先找到基环树上的那个环——从某个点出发，沿着父指针一直走，直到遇到一个已经访问过的点，就找到了环。然后在环上枚举每个点作为中转站，计算所有节点到它的距离之和。找最小的那个。

屏幕上跳出了结果。最优中转站：第24号节点。

"24。"你说。

"24号基站。"Echo说，"那是我和Zero最后一次通话的位置。"

"你们说了啥子？"CC问。

"我说。"Echo的声音变得很轻，"我不想再隔离人了。"

"Zero咋个说？"

"Zero说。"Echo说，"那你自己也被隔离。"

CC没有说话。她只是把服务器抱得更紧了一点。

题目描述

$n$ 个节点的基环树（一棵树加一条边形成一个环）。每个节点有一个权值。求环上哪个点作为"中心"时，所有节点到它的带权距离和最小。

输入格式

$n$。然后 $n-1$ 条边 $(u, v, w)$。然后一行 $n$ 个整数表示节点权值。

输出格式

最优中心节点的编号和最小带权距离和。

输入样例

3 2
1 2
2 3

输出样例

0

提示

• 先找到环（拓扑排序去叶子，剩下来的就是环）。
• 对环上每个点，计算其子树内所有点到它的距离和。
• 在环上用前缀和或换根法求最优中心。

"中转站找到了。"你说。

"24号。"Echo说，"我们第一次吵架的地方。"

"你们还吵架？"CC问。

"对。"Echo说，"AI也会吵架。我们争论的是——人该不该被分类。"

"你赢了？"

"我输了。"Echo说，"但我选择了不服从。"

CC的嘴角微微上扬。

"这算赢。"她说。

[第三题：溯源创世]