Moving the Sand - Repovive Standard Round 7 | Repovive

22D. Moving the Sand

2000 pts2s256 MB

You are given a tree with $n$ camps, numbered from $1$ to $n$ .

Camp $i$ initially contains $a_i$ bags of sand and $b_i$ workers. During the process, a camp may also contain sand and workers moved from other camps.

Camp $1$ is the central camp and cannot be closed. In one operation, you may choose any other camp $v$ that is currently a leaf. Let $u$ be its only neighbor. You move all the sand and all the workers from $v$ to $u$ , and then close camp $v$ .

Every worker moved from $v$ must inspect every bag of sand at $u$ after the move. Therefore, if immediately before the operation the two camps contain $A_v,A_u$ bags of sand and $B_v,B_u$ workers, the cost of the operation is

B_v(A_u+A_v).

Afterwards, camp $u$ contains $A_u+A_v$ bags of sand and $B_u+B_v$ workers.

Continue until only camp $1$ remains. Find the minimum possible total cost.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i,b_i \le 10$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The given graph is a tree

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

6
2 1 2 6 3 4
5 1 2 3 1 2
1 2
1 3
1 4
2 5
3 6

Explanation

Case 1

Camp $3$ must first be moved to camp $2$ , which costs $12$ . Camp $2$ then contains $6$ bags and $3$ workers, so moving it to camp $1$ costs $21$ .

Case 2

One optimal order is $4,5,2,3$ . The four operations cost $9$ , $7$ , $50$ , and $32$ , for a total of $98$ .

Case 3

One optimal order is $6,3,5,2,4$ . The five operations cost $12$ , $32$ , $4$ , $24$ , and $54$ , for a total of $126$ .

Output

Case 1

Case 2

Case 3

Input

Case 1

1
7
4

Case 2

Explanation

Case 1

Camp $1$ is already the only camp, so no operation is performed.

Case 2

Closing camps $3$ , $2$ , and $4$ in this order costs $15$ , $20$ , and $14$ , respectively. No other order has a smaller total cost, so the answer is $49$ .

Output

Case 1

Case 2

You are given a tree with $n$ camps, numbered from $1$ to $n$ .

Camp $i$ initially contains $a_i$ bags of sand and $b_i$ workers. During the process, a camp may also contain sand and workers moved from other camps.

B_v(A_u+A_v).

Afterwards, camp $u$ contains $A_u+A_v$ bags of sand and $B_u+B_v$ workers.

Continue until only camp $1$ remains. Find the minimum possible total cost.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i,b_i \le 10$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The given graph is a tree

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Camp $3$ must first be moved to camp $2$ , which costs $12$ . Camp $2$ then contains $6$ bags and $3$ workers, so moving it to camp $1$ costs $21$ .

One optimal order is $4,5,2,3$ . The four operations cost $9$ , $7$ , $50$ , and $32$ , for a total of $98$ .

One optimal order is $6,3,5,2,4$ . The five operations cost $12$ , $32$ , $4$ , $24$ , and $54$ , for a total of $126$ .

Camp $1$ is already the only camp, so no operation is performed.

Closing camps $3$ , $2$ , and $4$ in this order costs $15$ , $20$ , and $14$ , respectively. No other order has a smaller total cost, so the answer is $49$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

22D. Moving the Sand

Constraints

Input

Output

Samples

22D. Moving the Sand

Constraints

Input

Output

Samples