D. Function Ordering
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a rooted tree consisting of $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Vertex $$$1$$$ is the root.

Each vertex $$$v$$$ initially stores a function

$$$$$$ f_v(x) = a_v x + b_v, $$$$$$

where $$$a_v$$$ and $$$b_v$$$ are positive integers.

You have to perform the following operation exactly $$$n-1$$$ times until only the root vertex remains:

  1. Choose a vertex $$$u$$$ $$$(u \neq 1)$$$ that is currently a leaf in the tree.
  2. Let $$$p$$$ be the parent of $$$u$$$.
  3. Update the function stored at vertex $$$p$$$ to be the composition of the function at $$$u$$$ and the current function at $$$p$$$: $$$$$$ f_p(x) \leftarrow f_u(f_p(x)) $$$$$$
  4. Remove vertex $$$u$$$ and the edge $$$(u, p)$$$ from the tree.

After $$$n-1$$$ operations, only vertex $$$1$$$ remains with a final function $$$F(x)$$$. Your task is to maximize the value of $$$F(0)$$$.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the number of vertices.
  • Each of the next $$$n$$$ lines contains two integers $$$a_v$$$ and $$$b_v$$$ $$$(1 \le a_v, b_v \le 10^9)$$$ — the coefficients of the function at vertex $$$v$$$.
  • Each of the next $$$n-1$$$ lines contains two integers $$$p$$$ and $$$v$$$ $$$(1 \le p, v \le n)$$$, indicating that $$$p$$$ is the parent of $$$v$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the edges form a valid rooted tree with root $$$1$$$.

Output

For each test case, print a single integer — the maximum possible value of $$$F(0)$$$.

It is guaranteed that, for all inputs, the maximum possible value of $$$F(0)$$$ fits in a signed 64-bit integer.

Example
Input
2
3
1 5
4 2
2 3
1 2
1 3
5
2 1
2 3
3 1
2 2
4 1
1 2
1 3
2 4
2 5
Output
54
148
Note

In the first test case, the root is $$$1$$$ with $$$f_1(x) = x + 5$$$.

Its children are $$$2$$$ [$$$f_2(x) = 4x + 2$$$] and $$$3$$$ [$$$f_3(x) = 2x + 3$$$].

  • If vertex $$$2$$$ is deleted first and then vertex $$$3$$$: $$$f_1(x) := f_3(f_2(f_1(x))) = 2(4(x+5)+2)+3 = 8x + 47$$$. $$$F(0) = 47$$$.
  • If vertex $$$3$$$ is deleted first and then vertex $$$2$$$: $$$f_1(x) := f_2(f_3(f_1(x))) = 4(2(x+5)+3)+2 = 8x + 54$$$. $$$F(0) = 54$$$.
The maximum value is $$$54$$$.

In the second test case, one optimal deletion order is $$$4, 5, 2, 3$$$. The final function is $$$96x + 148$$$, so the answer is $$$148$$$.