题目内容

给定一棵以 $1$ 为根的树，共有 $n$ 个节点，每个节点 $i$ 有一个权值 $w_i$。定义节点深度：根节点深度为 $1$，子节点深度为父节点深度加 $1$。初始总代价 $C = \sum_{i=1}^n d_i \cdot w_i$，其中 $d_i$ 为节点 $i$ 的初始深度。

你可以执行至多一次操作：选择一个非根节点 $u$，将以 $u$ 为根的整个子树从其当前父节点处剪下，然后直接挂到根节点 $1$ 下，使其成为根节点的孩子。操作后，子树内所有节点的深度都减少 $d_u - 2$。

你的目标是使操作后的总代价尽可能小。请求出最小可能的总代价。

约束：

• 节点总数 $n$ 满足 $1 \le n \le 10^5$。
• 权值 $w_i$ 满足 $1 \le w_i \le 10^8$。