#CF2266G. Modular Tree

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

Modular Tree

题目描述

Vihaan 有一棵 nn 个节点的有根树∗^{\text{∗}},根节点为节点 11。

每个节点 ii 有一个初始值 aia_i 和一个模数 bib_i。设 xix_i 为节点 ii 的当前值。初始时 xi=aix_i=a_i。

Vihaan 可以执行以下操作任意次:

  • 选择一个节点 uu。设 ss 为 uu 的所有直接子节点的当前值之和,然后将 xux_u 替换为 (xu+s) mod bu(x_u+s)\bmod b_u。

在执行任意次操作后,Vihaan 希望使所有节点的值之和最大化。

求最大可能的和。

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

输入格式

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)— 测试用例的数量。

每个测试用例的第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)— 树中节点的数量。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai<bi0 \le a_i \lt b_i)— 节点的初始值。

第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n(1≤bi≤1091 \le b_i \le 10^9)— 节点的模数。

接下来 n−1n-1 行,每行包含两个整数 uu 和 vv(1≤u,v≤n1 \le u,v \le n)— 节点 uu 和 vv 之间的一条边。

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

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

输出格式

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

样例

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

说明

在第一个测试用例中,节点 11 没有子节点,因此对它执行操作不会改变其值。因此,最大可能的和为 33。

在第三个测试用例中,Vihaan 可以对节点 11 执行三次操作:

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

最终的和为 6+2+3=116+2+3=11。可以证明没有操作序列能得到更大的和。

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

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

最终的和为 4+1+1=64+1+1=6。可以证明没有操作序列能得到更大的和。