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.

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

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.