Migrated from Lutece 315 新手训练02_树的划分

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一棵树上每个节点有一个权值。求去掉一条边之后，两棵子树上节点权值之和相差最小，输出这个差值。

Input

第一行输入$n$ ($2\leq n\leq 10^5$)，表示树有$n$个节点（编号$0$到$n-1$）

第二行输入$n$个数，第$i$个数$C_i$表示表示节点$i-1$的权值 ($-10^4\leq C_i\leq 10^4$)

第三行输入$n-1$个数，第$i$个数$P_i$表示节点$i$的父亲,即节点$i$和节点$P_i$之间有一条边($0\leq P_i < i$)

Output

一个数，表示最小的差值

Samples

5
1 1 1 1 1
0 0 1 1

1

Resources

qbwj