410567: GYM104053 A Alice and Her Lost Cat

Alice wants to find her lost cat in the park.

The park is a rooted tree consisting of $$$n$$$ vertices. The vertices are numbered from $$$1$$$ to $$$n$$$, and the root is vertex $$$1$$$.

Alice is now at vertex $$$1$$$. She knows that the cat has run from vertex $$$1$$$ to some leaf of the tree, and no vertex is visited more than once. A leaf is a vertex without children.

There is a monitor on each vertex. The monitor on vertex $$$i$$$ can observe whether cat has visited vertex $$$i$$$ and which vertex the cat has gone to (if vertex $$$i$$$ is not a leaf). It takes $$$a_i$$$ seconds for Alice to check the data of the $$$i$$$-th monitor.

Alice can also search some leaves by herself. It takes $$$t_i$$$ seconds to search $$$i$$$ leaves. Note that $$$i$$$ is the count of vertices instead of the label of a vertex.

Help Alice to determine which monitors to be checked and which leaves to be searched so that the location of the cat can be uniquely determined, and the total time needed is minimum possible. Note that the monitors to be checked and the leaves to be searched should be decided at the beginning, and should not change after that.

Find the minimum time.

Each test contains multiple test cases.

The first line contains one single integer $$$T$$$ ($$$1 \le T \le 10$$$) denoting the number of test cases. The description of the $$$T$$$ test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \le 2000$$$) — the size of the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1 \le a_i \le 10^{9}$$$).

The third line of each test case contains $$$n$$$ integers $$$t_1,t_2,\dots,t_n$$$ ($$$1 \le t_i \le 10^{9},t_i\le t_{i+1}$$$).

Then $$$n-1$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$1\leq x,y\leq n,x \ne y$$$) denoting an edge connecting vertex $$$x$$$ with vertex $$$y$$$. It is guaranteed that these edges form a tree.

For each test case, output an integer in one line — the minimum time needed to determine the cat's location.

2
8
4 2 5 2 4 2 3 2
5 5 6 7 8 9 10 13
1 2
2 3
1 4
1 5
4 6
3 7
5 8
8
4 2 3 3 2 4 4 3
4 6 8 8 9 9 14 17
1 2
2 3
3 4
3 5
4 6
3 7
3 8

4
3