G. Модульное дерево
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Вихаана есть корневое дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин. Корень дерева находится в вершине $$$1$$$.

Каждая вершина $$$i$$$ имеет начальное значение $$$a_i$$$ и модуль $$$b_i$$$. Пусть $$$x_i$$$ обозначает текущее значение вершины $$$i$$$. Изначально $$$x_i=a_i$$$.

Вихаан может выполнять следующую операцию любое количество раз:

  • Выбрать вершину $$$u$$$. Пусть $$$s$$$ — сумма текущих значений всех детей вершины $$$u$$$, тогда заменить $$$x_u$$$ на $$$(x_u+s)\bmod b_u$$$.

После выполнения любого количества операций Вихаан хочет максимизировать сумму значений всех вершин.

Определите максимальную возможную сумму.

$$$^{\text{∗}}$$$Дерево — это неориентированный связный граф, в котором нет циклов.

Входные данные

В первой строке дано целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальную возможную сумму значений всех вершин после выполнения любого количества операций.

Пример
Входные данные
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
Примечание

В первом наборе входных данных у вершины $$$1$$$ нет детей, поэтому выполнение операции над ней не изменяет её значение. Следовательно, максимальная возможная сумма равна $$$3$$$.

В третьем наборе входных данных Вихаан может выполнить операцию над вершиной $$$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$$$. Можно показать, что никакая последовательность операций не может дать большую сумму.

В четвёртом наборе входных данных Вихаан может выполнить следующие операции:

  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$$$. Можно показать, что никакая последовательность операций не может дать большую сумму.