Problem Description

Bobi wakes up every morning to feed his favorite pets: ants. He places them in a glass bottle with a pipe system that can be represented as a tree with $n$ nodes. The pipes are represented by the edges of the tree. The root of the tree is located at the node labeled $1$. Inside the pipe system, due to gravity, liquid flows from a node to its child nodes. We know the flow rate $x_i$ for each pipe: the percentage of flow from the parent node to the child node. Consider the following example:

In the image, node $1$ has $12$ liters of liquid, and there are two pipes. One has a flow rate of $x_i=30$, and the other is $x_i=70$. Node $2$ will receive $3.6$ liters, and node $3$ will receive $8.4$ liters. In the input data, the sum of flow rates from the same node always equals $100$. Some of Bobi's pipes are not ordinary; they are super pipes with the ability to square the flow of liquid passing through them. In the previous example, if the first pipe had this ability, node $2$ would receive $12.96$ liters, while node $3$ would still receive $8.4$ liters. Note that the outflow of liquid from a node can exceed the inflow, which is why these pipes are super pipes!

All super pipes can be turned on or off by Bobi. Ants live only in the leaves of the tree (nodes without children). For each leaf, we know how much liquid is needed to feed the ants living there. Bobi wants to pour $L$ liters of liquid into the root to feed the ants. He doesn't have much money, so he wants to know the minimum amount of liquid he needs to purchase to ensure all ants are fed.

Input Format

The first line of input contains the integer $n$.

Each of the following $n-1$ lines contains four integers $a_i, b_i, x_i, t_i$, where $a_i$ and $b_i$ are the endpoints of the pipe (the numbers of the connected nodes), $x_i$ is the flow rate of liquid through the pipe, and $t_i$ indicates whether the pipe has super powers. If $t_i$ is $1$, the pipe has super powers; otherwise, it does not.

The next line contains $n$ integers $k_i$, describing the amount of liquid needed for the ants in the $i$-th node. If the $i$-th node is not a leaf, $k_i$ will be $-1$.

Output Format

Output a single line containing $L$.

Note: This problem uses a Special Judge (SPJ). Solutions will be considered correct if the error is within $10^{-3}$ of the correct answer.

Sample Input and Output

Sample Input #1

5
1 2 50 0
1 3 50 0
2 4 25 0
2 5 75 1
-1 -1 4 1 9

Sample Output #1

8.00

Sample Input #2

3
1 2 20 1
1 3 80 1
-1 4 8

Sample Output #2

10.0000

Sample Input #3

6
1 2 100 1
2 3 20 0
2 4 20 0
2 5 60 0
4 6 100 1
-1 -1 1 -1 1 2

Sample Output #3

2.659

Notes/Hints

Sample 1 Explanation

If Bobi injects $8$ liters of liquid into the root, node $3$ receives $4$ liters, node $4$ receives $1$ liter, and node $5$ receives $9$ liters. These amounts are the minimum required for the ants in the leaves. Therefore, $8$ liters is the minimum amount of liquid needed to satisfy the ants' condition.

Data Constraints

For $100\%$ of the data, $1 \le n \le 10^3$, $1 \le a_i, b_i \le n$, $1 \le x_i \le 100$, $t_i \in \{0, 1\}$, and $k_i \in [1, 10]$.

The value of $L$ will not exceed $2 \times 10^9$.

Notes

This problem is translated from COCI2014-2015 CONTEST #4 T4 MRAVI.

见题面 Input 部分

见题面 Output 部分