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 N1 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 



First test case :
Information
 ID
 1078
 Difficulty
 7
 Category
 Graph_Theory  DFS , BFS , Shortest_Path Click to Show
 Tags
 # Submissions
 49
 Accepted
 10
 Accepted Ratio
 20%
 Uploaded By
Related
In following contests: