World Tree

The bravest warrior PP got injured in an important battle. To save his life, the King decides to turn to the World Tree for help. The World Tree has much life energy that can cure the injury and one must find the energy point to receive the bless of the World Tree.

On the World Tree, there are $n$ energy points connected by $n-1$ bidirectional branches. Every energy point will have a unique energy value $b_i$. PP needs to start from the energy point labeled by $1$ to find every energy point on the tree to cure himself. After PP arrives at some energy point $i$, the life energy will perceive the existence of PP and its energy value will change into $a_i$. This change will result in a great much life energy and PP will get healed with it.

Specifically, the exact energy value he can get at a point is the product of the energy value at the point and the sum of the energy value of all points he has not visited. That is $a_i \times (\sum_{j} b_j)$ where point $i$ is the current point and $j$ iterates over all the points that has not been visited.

The principle PP chooses the path is that PP only considers the directions that he is able to get more energy. That is to say, PP will only return to the previous energy point when there is no more energy points in other directions.

PP need you to help him find the best path to get the most life energy value from the World Tree.

The first line of the input contains one integer $T$ $(1 \leq T \leq 10)$, indicating the number of test cases.

Then $T$ test cases follow.

The first line of each test case contains a single integer $n$ $(1\leq n\leq 10^5)$ - the number of energy points.

The second line contains $n$ integers $b_1,b_2,\ldots,b_n$ $(1\leq b_i\leq 100)$ - the energy value before changing. The third line contains $n$ integers $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 100)$ - the energy value after changing.

Each of the next $n-1$ lines contains two integers $x,y$ $(1\leq x,y\leq n)$, indicating the two energy point connected by the branch.

Output $T$ lines. For each test case, output a single integer in one line, indicating the maximal life energy value PP can get.

1
3
1 2 3
3 4 5
1 2
1 3

27

“红旗杯”第十四届吉林省大学生程序设计竞赛