Fxx and tree
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 131072/65536 K (Java/Others)
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?
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)
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”.
BestCoder Round #89