Like always Alice and Bob are playing games. Alice gives Bob a tree and challenged him in the following game :
The tree has some points in every node.
Bob can start from any node and stop at any node.
When Bob visits a node the point of this node is added to Bob’s score and points of this node become zero.
In each move, Bob can go to any adjacent node which has a positive score or finish the game at the current node with equal probability.
At the end of the game, If Bob’s score is divisible by two then he will be the winner otherwise Alice will be the winner.
Now Alice wants to know the probability of his winning in this game. As Bob is busy thinking about why the name of this problem is “Maze Runner”, he needs your help to solve this problem.
Input
Input starts with an integer T which denotes the number of the test cases. The first line of each test case is an integer N which is the number of nodes in the tree. The next line contains N integers which are the points of each node. In the next N-1 line, there will be two integers U and V which indicate there is an undirected edge between nodes U and V.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ points ≤ 1000
- 1 ≤ U, V <= N and U ≠ V
Output
For each test case output a real number which is the probability value which is asked in the problem. You'll get accepted if the difference between your answer and the standard answer is no more than 10-6.
Sample
| Input | Output |
|---|---|
2 3 2 2 2 1 2 1 3 6 2 1 1 1 1 1 1 2 2 3 3 5 3 6 2 4 | 0.0000000000 0.5714285714 |
In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.
