LCA的贡献

题目描述

给出一棵 $n$ 个节点的树，默认 $1$ 号节点为根。每一个节点有一个权值 $x_i$。

现在给你一个数组 $a$，$a_1,a_2,\dots,a_n$，这个数组是一个 $1\sim n$ 的排列。

对于 $a$ 数组的任意区间 $[l,r]$（$l \le r$），这个区间 $a_l,a_{l+1},\dots,a_r$ 这些节点的 LCA 是 $k$，那么这个区间的贡献就是 $x_k$。

最后求 $a$ 数组的所有区间的贡献总和。

输入格式

第 $1$ 行一个数 $n$，表示节点的个数。

第二行 $n-1$ 个数，第 $i$ 个数是 $p_{i+1}$。$p_i$ 表示节点 $i$ 的父亲是 $p_i$。数据保证 $p_i < i$。

第三行 $n$ 个数表示一个排列，$a_1,a_2,\dots,a_n$。

第四行 $n$ 个数，$x_1,x_2,\dots,x_n$，表示节点的权值。

输出格式

输出一个数表示答案。

样例

样例输入

5
1 1 1 1
5 2 3 1 4
31244 44588 57025 99626 20260

样例输出

565183

数据范围

对于 $20\%$ 的数据，$n \le 100$；

对于 $40\%$ 的数据，$n \le 2000$；

对于 $60\%$ 的数据，$n \le 50000$；

对于另外 $20\%$ 的数据，排列 $a_i$ 是用如下的算法生成的：从一号点开始对树做 dfs，到达一个节点的时候输出这个节点。

对于全部数据，$n \le 200000$，$0 \le x_i \le 100000$，$p_i < i$，$a_i$ 是一个排列。