#CF2266G. Modular Tree

    ID: 2647 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>深度优先搜索动态规划贪心数学数论树论Codeforces

Modular Tree

Problem Description

Vihaan has a rooted tree$^{\text{∗}}$ with $n$ nodes. The tree is rooted at node $1$.

Each node $i$ has an initial value $a_i$ and a modulus $b_i$. Let $x_i$ denote the current value of node $i$. Initially, $x_i=a_i$.

Vihaan may perform the following operation any number of times:

  • Choose a node $u$. Let $s$ be the sum of the current values of all direct children of $u$, then replace $x_u$ with $(x_u+s)\bmod b_u$.

After performing any number of operations, Vihaan wants to maximize the sum of the values of all nodes.

Determine the maximum possible sum.

$^{\text{∗}}$A tree is an undirected connected graph in which there are no cycles.

Input Format

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

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of nodes in the tree.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \lt b_i$) — the initial values of the nodes.

The third line contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1 \le b_i \le 10^9$) — the moduli of the nodes.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$) — an edge between nodes $u$ and $v$.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output Format

For each test case, print one integer — the maximum possible sum of the values of all nodes after performing any number of operations.

Examples

8
1
3
7
2
0 3
5 4
1 2
3
0 2 3
7 3 4
1 2
2 3
3
0 0 1
5 2 2
1 2
2 3
4
1 2 3 4
10 3 4 5
1 2
1 3
1 4
3
0 1 3
10 2 4
1 2
1 3
5
0 0 1 2 3
12 6 9 3 4
1 2
1 3
2 4
3 5
4
0 999999999 999999999 999999999
1000000000 1000000000 1000000000 1000000000
1 2
1 3
1 4
3
7
11
6
18
12
27
3999999996

Note

In the first test case, node $1$ has no children, so performing an operation on it does not change its value. Thus, the maximum possible sum is $3$.

In the third test case, Vihaan can perform the operation on node $1$ three times:

  1. $[0,2,3] \to [2,2,3]$.
  2. $[2,2,3] \to [4,2,3]$.
  3. $[4,2,3] \to [6,2,3]$.
The resulting sum is $6+2+3=11$. It can be shown that no sequence of operations can obtain a larger sum.

In the fourth test case, Vihaan can perform the following operations:

  1. Perform the operation on node $2$: $$[0,0,1] \to [0,1,1].$$
  2. Perform the operation on node $1$ four times: $$[0,1,1] \to [1,1,1] \to [2,1,1] \to [3,1,1] \to [4,1,1].$$
The resulting sum is $4+1+1=6$. It can be shown that no sequence of operations can obtain a larger sum.

Source

Imported from Codeforces — Codeforces Round 1122 (Div. 3).