P10555 [ICPC 2024 Xi'an I] Fix the Tree

给定一棵由 $n$ 个顶点组成的树。树中每个顶点 $i$ 都有一个值 $w_i$。 现在顶点 $u$ 将被破坏。一旦被破坏，顶点 $u$ 和所有以 $u$ 为一端的边将从树中移除。 为了使树重新连通，你可以执行以下操作任意次（可能为零次），顺序不限： - 首先从树中选择两个顶点 $u$ 和 $v$； - 然后支付 $w_u + w_v$ 个硬币，并在顶点 $u$ 和 $v$ 之间添加一条边； - 最后，将 $w_u + 1$ 替换为 $w_u$，将 $w_v + 1$ 替换为 $w_v$。 你的任务是计算需要支付的最小硬币数。 但你不知道哪个顶点是 $u$，所以你需要为每个 $1 \le u \le n$ 找到答案。请独立回答所有查询。

无

无

给定一个有 $n$ 个点组成的树，每个点有一个权值 $w_i$。 点 $u$ 和相邻的边被删除。 你可以进行以下操作任意次数（可以为 $0$），让树重新成为连通图： 1. 选择两个点 $u$、$v$； 2. 花费 $w_u + w_v$ 的代价连接一条边 $(u,v)$； 3. $w_u \leftarrow w_u+1, w_v \leftarrow w_v+1$。 对于每个 $u$ 计算最小代价。（由 ChatGPT 4o 翻译）