Apple on Tree

Apple on Tree

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given a tree with N nodes.There are some node has apple. You need to collect of the all apple. In one move you can go any neighbor nodes, it will take exactly one second. You can start from any node and stop any node. Find the minimum numbers of seconds need to collect all available apples in the nodes.

Let's see a figure :

Input

In the first line T, number of test cases.
In each test case,
First line N, the number of the nodes.
Second line an array \(A[]\) and the length of the array is N. If \(A_i\) = 1, that means \(i_{th}\) node has a apple, Otherwise not.
Third line exactly N-1 edges between U and V.

\(1<=T<=10^3\)
\(1<=N<= 2 * 10^5\)
\(A[] = {0,1}\)
\(1<= U,V<=N\)

It is gruantte that sum of N over all test case doesn't exceed \(2 * 10^5\)
Graph is a tree.

Output

In each test cases, print the minimum second required to collect available apple in the tree.
Note : If there is no apple in the tree print 0.

Sample

Input Output
2
8
0 0 1 1 1 0 0 0
1 2
2 5
2 4
4 7
4 8
1 3
3 6
3
0 1 0
1 2
2 3
5
0

First test case :

Information

ID
1078
Difficulty
6
Category
Graph_Theory | DFS , BFS , Shortest_Path Click to Show
Tags
# Submissions
86
Accepted
23
Accepted Ratio
27%
Uploaded By

Related

In following contests:

Bangladesh 2.0