题目描述

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.

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.

题目大意

给定一个 $n(1\le n\le10^5)$ 个节点的树，每个节点上有 $a_i$ 只晶蝶。派蒙最初在 $1$ 号节点，并获得 $1$ 号节点的所有晶蝶，接下来每一秒她可以移动到相邻的节点上并获得节点上的所有晶蝶，但是当她每到达一个节点 $u$ 后，对于每个与 $u$ 相邻的节点 $v$，节点 $v$ 上的的晶蝶会在 $t_v(1\le t_v\le3)$ 秒内消失，在 $t_v$ 秒后再到达节点 $v$ 将无法获得节点上的晶蝶。现在需要你求出最多可以获得的晶蝶数。

2
5
1 10 100 1000 10000
1 2 1 1 1
1 2
1 3
2 4
2 5
5
1 10 100 1000 10000
1 3 1 1 1
1 2
1 3
2 4
2 5

10101
10111

提示

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.