407506: GYM102803 J Jingle Bells

Chino has $$$n$$$ jingle bells, and she plans to decorate them on the Christmas tree one by one.

However, this Christmas tree is strange. This tree has $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$. Each node has two value $$$a_i, b_i$$$. When Chino puts a jingle bell on node $$$i$$$, she will gain beauty value. Formally, after putting one jingle bell, let $$$S$$$ be the set of nodes which contains at least one jingle bell, she will get $$$b_i \times \sum_{j \notin S} a_j$$$ points.

At the beginning, Chino can only put bells on the root node of the Christmas tree and get $$$0$$$ points. Then Chino can put jingle bells on any node $$$v$$$ satisfying $$$(u,v) \in E(G), u \in S, v \notin S$$$ and get its beauty value.

Chino want to make Christmas tree the most beautiful, but she don't know the maximum beauty value she can get. Can you help her?

The first line contains an integer $$$n ~ (1 \leq n \leq 100000)$$$ denoting the numbers of nodes and jingle bells.

The second line contains $$$n-1$$$ integers $$$f_2, f_3, \cdots, f_n$$$, and $$$f_i$$$ represents the parent of node $$$i$$$ is node $$$f_i ~ (1 \leq f_i < i)$$$.

The next $$$n$$$ lines each contains $$$2$$$ integers $$$a_i, b_i ~ (0 < a_i, b_i \leq 10000)$$$, which is for the node value $$$a_i, b_i$$$. It is guaranteed that $$$a_1 = b_1 = 0$$$.

One line with one integer denoting the maximum beauty value.

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

14

10
1 1 2 2 3 3 6 6 6
0 0
4 1
5000 1
3 1
6 1
200 1
1 1
1 1
1 1
1 1

16040

For the first sample, we can put the jingle bells in the order of $$$1 - 2 - 4 - 3$$$.