g6-07505. 带权配对·最大收益

题目描述

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点，每条边有一个正整数收益。选出若干条边，要求任意两条被选的边没有公共端点，使被选边的收益之和最大。

允许一条边都不选，此时收益之和为 $0$ 。

第一行一个整数 $n$ 。

第二行 $n - 1$ 个整数 $w_{2}, w_{3}, \dots, w_{n}$ ，其中 $w_{i}$ 表示边 $(f_{i}, i)$ 的收益（ $n = 1$ 时该行为空）。

第三行 $n - 1$ 个整数 $f_{2}, f_{3}, \dots, f_{n}$ ，其中 $f_{i}$ 表示结点 $i$ 的父亲，保证 $f_{i} < i$ （ $n = 1$ 时该行为空）。

一行一个整数，表示最大收益之和。

输入：

3
5 7
1 1

输出：

树是 $1$ 号下挂 $2, 3$ 。边 $(1, 2)$ 收益 $5$ 、 $(1, 3)$ 收益 $7$ ，两条边共端点 $1$ ，只能选一条，取收益 $7$ 。

输入：

4
10 20 30
1 2 3

输出：

树是一条链 $1 - 2 - 3 - 4$ 。选边 $(1, 2)$ 与 $(3, 4)$ ：收益 $10 + 30 = 40$ ，两两不共端点。