题面

苦竹岭无归去日，海棠花落旧栖枝。

春风三月，诗岸独自一人离家求学。在西北的某座城市里，花开正好。

这颗樱花树对诗岸来说，是一颗 $n$ 个点的树，其中第 $i$ 个点上的开的花有观察值 $a_i$ ，这代表对诗岸来说看到这朵花，会让她增加 $a_i$ 的悲伤度。

诗岸将在树前站立 $10^{2025}$ 秒，其中每一秒中会发生两件事：

首先，每一朵这一秒仍然存在于树上的花会对诗岸产生悲伤度，使得诗岸观察花朵的悲伤度总和增加这些花朵的观察值 $a_i$ 之和。

接着，诗岸将采摘一些花朵，被采摘的花朵将离开树上，从而无法在后续的观测中影响诗岸。但由于诗岸对于樱花树整体美观的考量，诗岸每次采摘的花朵直接两两不能有连边，这保证了樱花树每次都不会被采摘太多从而导致局部空白。

现在诗岸想问，在这漫长的时间内，她所产生的悲伤度总和最少是多少。

形式化表达：

给定一颗树 $T$，你需要选出若干独立子集（可为空） $S_1,S_i,....,S_{10^{2025}}$ 其中 $S_i \cap S_j = \varnothing$，$\cup_{i = 1}^{10^{2025}} S_i = T$

最小化 $\sum_{i = 1}^{10^{2025}} \sum_{j = i}^{10^{2025}} \sum_{x \in S_j} a_x$

输入格式

在所有输入前将输入 $id$ ，表示这一数据的测试编号，详情见数据范围。

数据第一行输入 $n$，代表位于诗岸面前的樱花树的大小。

数据第二行输入 $n$ 个数，其中第 $i$ 个数代表 $a_i$。

接下来 $n - 1$ 行，每行输入一个数 $f_i$，代表在树上存在 $(i + 1,f_i)$​ 这一条边，树保证以 $1$ 为根

同时请选手注意最后两档数据中的特殊输入格式

输出格式

输出一行数字，表示诗岸在漫长时光里能收到的最小的悲伤总和

数据范围

数据范围依从下表

subtask依赖：测试点 21-30 依赖测试点 9-18。

其中对于 $19$ 至 $30$ 组数据，由于输入过大，我们将给出数据的 $gen$ 和 $seed$

其中 $gen$ 为

int data_f[1000005],data_a[1000005];
long long r(){return (rand()<<15) + rand();}
inline void generate_deg(int seed){
	//....
}
inline void generate(int seed){
	//....
}

int main(){
    //id
    //if id in [19,20] use generate_deg
    //if id in [21,30] use generate
}

具体实现可以见下发文件 $gen.cpp$​，但保证本题做法与数据生成器无关。

在 $id = 19/20$ 时，通过输入的 $seed$ 调用 generate_deg 函数

在 $id = [21,30]$ 时，通过输入的 $seed$ 调用 generate 函数

输入数据将为对应 $\text{data\_a}_{1...n}$ 与 $\text{data\_f}_{1...n - 1}$

为方便选手我们提供了一个现成框架，可供选手参考,可以查看下发文件 $exp.cpp$

int data_f[1000005],data_a[1000005];
long long r(){return (rand()<<15) + rand();}
inline void generate_deg(int seed){
	//....
}
inline void generate(int seed){
	//....
}

int n;
int seed;

int main(){
    scanf("%d",&id);
    if(id < 19){
        scanf("%d",&n);
        for(int i = 1;i <= n;++i)scanf("%d",&data_a[i]);
        for(int i = 1;i < n;++i)scanf("%d",&data_f[i]);
    }
    if(id == 19 || id == 20){n = 1000000;scanf("%d",&seed);generate_deg(seed);}
    if(id > 20){n = 1000000;scanf("%d",&seed);generate(seed);}
}