31182번 - Crystalfly 다국어

문제

Paimon is catching crystalflies on a tree, which are a special kind of butterflies in Teyvat. A tree is a connected graph consisting of $n$ vertices and $(n - 1)$ undirected edges.

Pixiv ID: 93964680

There are initially $a_i$ crystalflies on the $i$-th vertex. When Paimon reaches a vertex, she can catch all the remaining crystalflies on the vertex immediately. However, the crystalflies are timid. When Paimon reaches a vertex, all the crystalflies on the adjacent vertices will be disturbed. For the $i$-th vertex, if the crystalflies on the vertex are disturbed for the first time at the beginning of the $t'$-th second, they will disappear at the end of the $(t' + t_{i})$-th second.

At the beginning of the 0ドル$-th second, Paimon reaches vertex 1ドル$ and stays there before the beginning of the 1ドル$-st second. Then at the beginning of each following second, she can choose one of the two operations:

• Move to one of the adjacent vertices of her current vertex and stay there before the beginning of the next second (if the crystalflies in the destination will disappear at the end of that second she can still catch them).
• Stay still in her current vertex before the beginning of the next second.

Calculate the maximum number of crystalflies Paimon can catch in 10ドル^{10^{10^{10^{10}}}}$ seconds.

입력

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ (1ドル \le n \le 10^5$) indicating the number of vertices.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ (1ドル \le a_i \le 10^9$) where $a_i$ is the number of crystalflies on the $i$-th vertex.

The third line contains $n$ integers $t_1, t_2, \cdots, t_n$ (1ドル \le t_i \le 3$) where $t_i$ is the time before the crystalflies on the $i$-th vertex disappear after disturbed.

For the next $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ (1ドル \le u_i, v_i \le n$) indicating an edge connecting vertices $u_i$ and $v_i$ in the tree.

It's guaranteed that the sum of $n$ of all the test cases will not exceed 10ドル^6$.

출력

For each test case output one line containing one integer indicating the maximum number of crystalflies Paimon can catch.

제한

노트

For the first sample test case, follow the strategy below.

• During the 0ドル$-th second
  • Paimon arrives at vertex 1ドル$;
  • Paimon catches 1ドル$ crystalfly;
  • Crystalflies in vertices 2ドル$ and 3ドル$ are disturbed.
• During the 1ドル$-st second
  • Paimon arrives at vertex 3ドル$;
  • Paimon catches 100ドル$ crystalflies.
• During the 2ドル$-nd second
  • Paimon arrives at vertex 1ドル$;
  • Crystalflies in vertex 2ドル$ disappears.
• During the 3ドル$-rd second
  • Paimon arrives at vertex 2ドル$;
  • Crystalflies in vertices 4ドル$ and 5ドル$ are disturbed.
• During the 4ドル$-th second
  • Paimon arrives at vertex 5ドル$;
  • Paimon catches 10000ドル$ crystalflies;
  • Crystalflies in vertex 4ドル$ disappears.

For the second sample test case, the optimal strategy is the same with the first sample test case. Crystalflies in vertex 2ドル$ are scheduled to disappear at the end of the 3ドル$-rd (instead of the 2ドル$-nd) second, allowing Paimon to catch them.