择枝而栖

换根完了，但每个矿工需要选择技能——择枝而栖。

"择枝？"CC问。

"对。"你说，"给定一棵树，每个节点有一个技能值。选一个节点作为基地，使得它到所有矿工的距离之和最小。"

"距离之和？"

"对。"你说，"基地到每个矿工的管道距离。"

"最小？"

"对。"你说，"找树的重心或最优根。"

"咋算？"

"树形DP+换根。"你说，"先算一个根的距离和，然后换根，更新距离和。"

"更新？"

"对。"你说，"如果把根从$u$换到$v$，距离和变化：$v$的子树节点距离减1，其他节点距离加1。"

"第47个节点。"你说，"如果它是基地，距离和是多少？"

"看树的大小和形状。"你说，"如果是平衡树，距离和小；如果是链，距离和大。"

"平衡好？"

"对。"你说，"平衡的树，基地在中间，大家距离都近。"

"像住小区？"

"对。"你说，"像住小区——中间有广场，大家去都方便。"

"如果住边上？"

"远。"你说，"边上的人去广场远，广场上的人去边上 also 远。"

"also？"

"对。"你说，"距离是对称的——$u$到$v$等于$v$到$u$。"

CC看着那棵树——像一个家，像一个社区，像某种需要选择中心的东西。

"选哪？"她问。

"算。"你说，"换根DP，算出每个节点当基地的距离和，选最小的。"

"能算出来？"

"能。"你说，"$O(n)$。"

Echo把择枝过程投射出来——每个节点的距离和像光环，有的亮，有的暗。

"以前我住在边上。"她说，"现在……想往中间挪。"

"因为中间热闹。"CC说。

"对。"Echo说，"因为中间热闹。

题目描述

给定一棵树，每个节点有一个权值（矿工数）。选一个节点作为基地，使得它到所有矿工的带权距离之和最小。

输入格式

第一行$n$。第二行$n$个整数权值。接下来$n-1$行，每行一条边。

输出格式

最小带权距离和。

输入样例

5
1 2 3 4 5

输出样例

-808464433

提示

• 树形DP求一个根的距离和。
• 换根：$sum[v]=sum[u]+(总权值-2\times subtree[v])$。
• 时间复杂度$O(n)$。