CF2266G.Modular Tree

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.

维汉有一棵含 $n$ 个节点的有根树$^{\text{∗}}$，树根为节点 $1$。

每个节点 $i$ 有一个初始值 $a_i$ 和一个模数 $b_i$。记节点 $i$ 的当前值为 $x_i$，初始时 $x_i = a_i$。

维汉可以任意次执行以下操作：

• 选择一个节点 $u$。令 $s$ 为 $u$ 的所有直接子节点的当前值之和，然后将 $x_u$ 替换为 $(x_u + s) \bmod b_u$。

在执行任意次数的操作后，维汉希望最大化所有节点的值之和。

请确定该和的最大可能值。

$^{\text{∗}}$ 树是一种无向连通图，其中不存在环。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 树中节点的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \lt b_i$）—— 各节点的初始值。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$1 \le b_i \le 10^9$）—— 各节点的模数。

接下来的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n$）—— 表示节点 $u$ 与节点 $v$ 之间的一条边。

保证所给的边构成一棵树。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一个整数——执行任意次数操作后，所有节点的值之和的最大可能值。

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.

在第一个测试用例中，节点 $1$ 没有子节点，因此对其执行操作不会改变其值。于是，可能的最大和为 $3$。

在第三个测试用例中，Vihaan 可以对节点 $1$ 执行三次操作：

1. $[0,2,3] \to [2,2,3]$。
2. $[2,2,3] \to [4,2,3]$。
3. $[4,2,3] \to [6,2,3]$。

最终得到的和为 $6+2+3=11$。可以证明，不存在任何操作序列能得到更大的和。

在第四个测试用例中，Vihaan 可以执行以下操作：

1. 对节点 $2$ 执行操作：$[0,0,1] \to [0,1,1]$。
2. 对节点 $1$ 执行四次操作：$[0,1,1] \to [1,1,1] \to [2,1,1] \to [3,1,1] \to [4,1,1]$。

最终得到的和为 $4+1+1=6$。可以证明，不存在任何操作序列能得到更大的和。