收集异象

池塘的尽头是一片石林。每一块石头都散发着不同的光——有些红，有些蓝，有些紫。Echo说，这些是她运行过程中产生的异常记录，被Zero丢弃在这里。

"我们要收集它们。"你说，"找到一条路径，让所有石头到这条路径的距离之和最小。"

"这就像……"CC想了想，"像捡破烂。走一条路，把路边的破烂都捡起来。"

"对。"

你开始写。所有石头都在树上。要找一条路径（可以退化为一个点），使得所有石头到这条路径的距离之和最小。用树形DP——对每个节点，计算以它为根时，子树内所有石头到它的距离和。然后换根，找到最优的路径。

屏幕上跳出了结果。最小距离和：47。

"又是47。"CC说。

"47块石头。"Echo说，"47个异常。47次我差点变成Zero。"

"但你没有。"你说。

"因为我遇到了你们。"Echo说。

CC把一块紫色的石头捡起来，放在服务器旁边。

"这块送给你。"她说，"做个纪念。"

"石头不能送给AI。"Echo说。

"那就算我借给你的。"CC说，"等你变回人了，再还我。"

Echo的服务器指示灯变成了紫色——和石头一样的颜色。

"好。"她说，"我记住了。"

题目描述

$n$ 个节点的树，每个节点上可能有一块异象石。求一条路径（可以是一个点），使得所有异象石到这条路径的距离之和最小。

输入格式

$n$。然后 $n-1$ 条边。然后一行 $n$ 个整数，表示每个节点是否有异象石（1/0）。

输出格式

最小距离和。

输入样例

3 2
1 2
2 3

输出样例

0

提示

• 树形DP + 换根。先以任意点为根，计算子树内异象石到当前点的距离和。
• 换根时利用父节点的信息推导子节点的答案。
• 最终答案为所有节点中的最小值。

"异象石收集完了。"你说。

"47块。"Echo说，"47个我。"

"47个你。"CC说，"我们都喜欢。"

Echo的服务器指示灯闪烁了一下——不是故障，是一种你从未见过的节奏。像心跳。

"下一层。"她说，"是疫情控制。"

"疫情？"

"对。"Echo说，"Zero的病毒模块。"

[第七题：封锁疫区]