g6-07616. 带权重心的重心 · 林老师的题库

题目描述

给定一棵以 $1$ 为根的有根树，每个结点有正权 $w_{i}$ 。删去结点 $u$ 后树分成若干块，记 $M (u)$ 为各块点权和的最大值。求 $M (u)$ 最小的结点（并列取编号最小）。

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $w_{1}, \dots, w_{n}$ 。

第三行 $n - 1$ 个整数 $f_{2}, \dots, f_{n}$ （ $n = 1$ 时该行为空）。

输入：

5
1 1 1 1 1
1 2 2 2

输出：

树： $1 - 2$ ， $2$ 连着 $3, 4, 5$ 。删 $2$ 得四块各 $1$ 个点（权 $1$ ）；删 $1$ 得含 $2, 3, 4, 5$ 的块权 $4$ ，所以 $2$ 是带权重心。