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) ∈ E(G),u ∈ 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 T (1 ≤ T ≤ 5) denoting the count of testcase.

For each testcase,

The first line contains an integer n (1 ≤ n ≤ 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 ≤ $f_i$ < i).

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

It is guaranteed that $\sum n ≤ 2.1\times 10^5$.

For each testcase, one line with one integer denoting the maximum beauty value.

2
4
1 1 2
0 0
3 1
5 1
4 1
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

14
16040

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

“红旗杯”第十五届黑龙江省大学生程序设计竞赛