g6-07611. 点权最长向下路径

题目描述

给定一棵以 $1$ 为根的有根树，每个结点有点权 $w_{i}$ （可为负）。求一条从某点出发、只往下走的简单路径（至少包含一个结点），使路径上点权之和最大。

第一行一个整数 $n$ 。

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

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

输入：

4
3 -1 5 2
1 1 2

输出：

取路径 $1 - 3$ ： $3 + 5 = 8$ ； $1 - 2 - 4$ ： $3 - 1 + 2 = 4$ 。最大为 $8$ 。