Fxx and tree

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/65536 K (Java/Others)

Description

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 "<b>3.7998</b>", you should output “3.800”.

Sample Input

1 2 1 2 0 0 1 0

Sample Output

3.000

Hint

wange2014

Source

BestCoder Round #89

提交代码