Description

The famous electronics brand SHOI has just released the next-generation product leading the global trend — the Probability Charger:

“Using brand-new nano-scale fabrication technology, whether components and wires conduct is determined entirely by true random numbers! The SHOI Probability Charger, an indispensable necessity in your life! Can it charge? Try it now!”

The SHOI Probability Charger connects $n$ charging components with $n-1$ wires. During charging, whether each wire can conduct is decided by probability, and whether each component charges directly is also decided by probability. Then electric energy can travel from components that charge directly, through conducting wires, to make other components charge indirectly.

As a loyal customer of SHOI, you cannot resist the impulse to buy SHOI products. After waiting in a long line for a week, you finally get the latest model of the SHOI Probability Charger. You eagerly plug it into the power source — and suddenly wonder: what is the expected number of components that enter the charging state?

Input Format

The first line contains an integer $n$, the number of charging components. The components are numbered $1 \sim n$.

Each of the next $n-1$ lines contains three integers $a, b, p$, describing a wire connecting components $a$ and $b$, with conduction probability $p\%$.

The $(n+1)$-th line contains $n$ integers $q_i$, meaning that component $i$ charges directly with probability $q_i\%$.

Output Format

Output one real number: the expected number of components that enter the charging state, rounded to 6 decimal places.

3
1 2 50
1 3 50
50 0 0

1.000000

5
1 2 90
1 3 80
1 4 70
1 5 60
100 10 20 30 40

4.300000

Hint

• Constraints:
  • For $30\%$ of the testdata, $n \leq 5 \times 10^3$.
  • For $100\%$ of the testdata, $n \leq 5 \times 10^5$, $0 \leq p, q_i \leq 100$.

Translated by ChatGPT 5