#CF2266G. Modular Tree
Modular Tree
题目描述
Vihaan 有一棵 个节点的有根树,根节点为节点 。
每个节点 有一个初始值 和一个模数 。设 为节点 的当前值。初始时 。
Vihaan 可以执行以下操作任意次:
- 选择一个节点 。设 为 的所有直接子节点的当前值之和,然后将 替换为 。
在执行任意次操作后,Vihaan 希望使所有节点的值之和最大化。
求最大可能的和。
树是一个无向连通图,其中不存在环。
输入格式
第一行包含一个整数 ()— 测试用例的数量。
每个测试用例的第一行包含一个整数 ()— 树中节点的数量。
第二行包含 个整数 ()— 节点的初始值。
第三行包含 个整数 ()— 节点的模数。
接下来 行,每行包含两个整数 和 ()— 节点 和 之间的一条边。
保证给定的边构成一棵树。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一个整数 — 执行任意次操作后所有节点值之和的最大可能值。
样例
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
说明
在第一个测试用例中,节点 没有子节点,因此对它执行操作不会改变其值。因此,最大可能的和为 。
在第三个测试用例中,Vihaan 可以对节点 执行三次操作:
- 。
- 。
- 。
最终的和为 。可以证明没有操作序列能得到更大的和。
在第四个测试用例中,Vihaan 可以执行以下操作:
- 对节点 执行操作:$$[0,0,1] \to [0,1,1].$$
- 对节点 执行四次操作:$$[0,1,1] \to [1,1,1] \to [2,1,1] \to [3,1,1] \to [4,1,1].$$
最终的和为 。可以证明没有操作序列能得到更大的和。