Karashi的树 I

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

题目描述

给定一棵由 $n$ 个节点组成的有根树（ $n$ 个节点 $n-1$ 条边形成的无向连通图），根为点1。节点 $i$ 的权值为 $a_i$ 。定义点 $i$ 的“根路径”为根到点 $i$ 形成的路径序列，即 $path_i=\{v_0,v_1,…,v_{len} \}(v_0=1,v_{len}=i)$ ；“根路径”权值序列即为 $\{a_{v_0},a_{v_1},…,a_{v_{len}}\}$ 。
现在你可以执行以下操作若干次：

选择一个节点 $i$ ，将其“根路径”的权值序列翻转。具体地说，对于其“根路径”权值序列 $\{a_{v_0},a_{v_1},…,a_{v_{len}}\}$ ，更改 $\{a_{v_0},a_{v_1},…,a_{v_{len}}\}\rightarrow \{a_{v_{len}},a_{v_{len-1}},…,a_{v_0}\}$ 。下图示例表示选择节点9进行操作。

定义这棵树的价值为每个节点的“根路径”权值序列之和的总和，即 $Val=∑_{i=1}^n∑_{x∈path_i}a_x$ 。求通过若干次操作后，这棵树的最大价值。

输入描述:

第一行包括一个正整数，表示树的节点数；
第二行包括个正整数，第个数表示最初每个节点的权值；
第三行包括个正整数，第个数表示节点的父节点。

输出描述:

输出一个正整数，表述经过若干次操作后，树的最大价值。

示例1

输入

复制

9
3 5 3 4 6 1 5 1 6
1 2 2 2 1 6 6 8

输出

复制