Young theoretical computer scientist Fxx has a tree.
You are given a rooted tree with n vertices,numbered from 1 to n(vertex 1 is the root).Each vertex of the tree has a value $A_i$ and a color,which is either black or white.
Now consider a reverse operation: Choose a vertex $X$ randomly.When X is chosen,its color changes.Meanwhile,the color of a vertex $K$ changes as well if and only if $X$ is an ancestor of $K$ and the distance between them is no more than $A_X$.
Fxx need to find out the expected number of operations to turn the whole tree black.Can you help him?
Input
In the first line, there is an integer $T(T\leq100)$ indicating the number of test cases.
For each test case,the first line contains one integers n(1\leq n\leq 50), indicating the number of vertice.
In the next n-1 lines, Each line contains two integers $u$ and $v$ meaning that vertice $u$ is the father of vertice $v$.
In the next line contains $n$ integers $A_1,A_2,\ldots,A_n(0\leq A_x\leq n)$.
In the next line contains $n$ integers $C_1,C_2,\ldots,C_n$, indicating the color of each vertice($C_x=0$ means the color of vertice $x$ is white, $C_x=1$ means the color of vertice $x$ is black)
Output
For each test case, output the answer.
Each answer is rounded to three decimal places.
For example,if the answer is "3.7998", you should output ¡°3.800¡±.
