Type: Default 3000ms 256MiB

L3-3 树的价值

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有 n 小球,要求把这 n 个球放到到一棵树上。

这棵树有 n 个节点,每个节点有两个值 ai,bi,每放一个球在节点 i ,就会得到一定的美丽值,如果在节点 i 放了球之后已经放有球节点集合为 S ,则可以获得 $$ bi×\sum_{j\notin S}aj $$ 点价值。

一开始只能把球放在树的根节点,并获得 0 点美丽值,随后可以把球放到任何一个点 v 满足 $$ ∃E(u,v),E∈G,u∈V,v∈V,u∈S,v∉S $$,并获得相应的价值。

如何才能获得最大的价值。

Format

Input

第一行一个整数 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 。

Output

一行一个整数表示最大价值。

Samples

4
1 1 2
0 0
3 1
5 1
4 1
14

Limitation

1s, 1024KiB for each test case.

2023团体程序设计天梯赛选拔赛

Not Attended
Status
Done
Rule
IOI
Problem
14
Start at
2023-3-19 14:00
End at
2023-3-19 17:00
Duration
3 hour(s)
Host
Partic.
46