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