题目背景
你所选择的道路是对你的试炼,很多情况下你会输的更惨,但那些坚持自己道路,永不放弃的人,终会在远方找到真正的黑暗
题目描述
hyj 有 n 点天赋值,他打算把这 n 点天赋点到自己的各项技能点上。
hyj 的天赋技能树是一棵奇怪的天赋技能树 G ,这个天赋树有 n 个节点,每个节点有两个值 ai,bi ,hyj 每点一点天赋在节点 ,那么就会得到一定的信仰值,我们假定在节点 i,点了天赋之后已经点了天赋的节点集合为 S ,则可以获得 bi×∑j∈/Saj 点信仰值。
一开始 hyj 只能把天赋点在天赋树的根节点,并获得 0 点信仰值,随后 hyj 可以把天赋点到任何一个点 v 满足 ∃E(u,v),E∈G,u∈V,v∈V,u∈S,v∈/S,并获得相应的信仰值。
hyj 不知道如何才能让信仰值变得最高(即成为混沌专精),你能帮他吗?
输入
第一行一个整数 n(1≤n≤100000) 表示天赋树的节点个数和总天赋点个数。
第二行 n−1 个整数,第 i 个整数 fi 表示第 i+1 个点的父亲是 fi(1≤fi≤i)。
接下去 n 行每行 2 个整数 ai,bi(0<ai,bi≤10000) ,表示节点 i 的 a,b 值,保证根节点 a1,b1均为 0 。
输出
一行一个整数表示最高信仰值。
样例
样例解释
样例解释:
对于第一个样例,我们可以把天赋点数按照这个顺序放 1−2−4−3 ,此时信仰值最高。