Crying 与哈密顿路

题号：NC264896
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Crying 正在寻找一张图的哈密顿路。

他首先给了你一棵 $n$ 个点的有根树，根为 $1$ ，第 $i$ 个点有点权 $w_i$ 。

通过这棵树，他要构造一张 $n$ 个点的边有权的无向完全图，其中边 $(u, v)$ 的权值为先前的有根树上 $u, v$ 的最近公共祖先的点权。

他想要你在新构造的这张图上找到经过的边的边权和最大的哈密顿路（即一条恰好经过每个点一次的路径），不过你只需给出这个边权和即可。

第一行，一个正整数 $n$ 。

第二行， $n$ 个整数 $w_1, w_2, \dots, w_n$ 。

第三行， $n-1$ 个正整数 $f_2, f_3, \dots, f_n$ ，其中 $f_i$ 表示有根树上 $i$ 的父亲。

对于所有数据， $1 \le n \le 300$ ， $|w_i| \le 10^9$ ， $1 \le f_i < i$ 。

一行，一个整数，表示最大的边权和。

示例1

复制

5
-1 2 -3 4 -5
1 1 3 3

复制

-4

一种可行的路径是 $3 \to 1 \to 4 \to 2 \to 5$ ，其中每条边边权都为 $-1$ 。

可以证明没有更优解。

示例2

复制

15
-13 3 -9 3 -12 4 3 9 3 -4 11 12 -13 -10 15
1 1 2 3 5 1 4 7 4 3 4 4 8 5

复制

-48