P9428 [Lanqiao Cup 2023 National B] Escape.

In Xiao Ming's galaxy, there are $n$ planets, numbered from $1$ to $n$. These planets are connected by $n - 1$ undirected edges, forming a tree. The root node is planet $1$. To escape to another galaxy when an interstellar war arrives, Xiao Ming sets an escape portal at the root. People on each planet only need to keep moving to the parent planet to reach the root. To make it easier for people on each planet to reach the root, Xiao Ming chooses $m$ planets as springboard planets. On the path from some planet to the root, when a person passes any planet (including the starting planet), they may try to jump directly to **the first springboard planet on their path to the root, excluding the current planet**. The time cost is the same as walking to the parent planet, both being $1$ unit of time. However, due to technical issues, a jump to a springboard planet may not succeed. Each jump fails with probability $p$, and then the person instead jumps to the parent planet of the current planet (equivalent to directly walking to the parent planet). At the same time, that springboard planet becomes invalid and will **no longer be considered a springboard planet**. To measure movement efficiency, Xiao Ming wants to know: if a person randomly chooses one of the $n$ planets as the starting point and heads to the root, what is the expected value of the minimum time cost, in units of time?

The input has $n + 1$ lines. The first line contains two positive integers $n$, $m$ and a floating-point number $p$. The next $n - 1$ lines each contain two positive integers $x_i, y_i$, representing the two endpoints of the $i$-th edge. The last line contains $m$ positive integers, representing the indices of all springboard planets.

One line containing a floating-point number, representing the answer (please keep two decimal places).

### Sample Explanation The time cost starting from planet $1$ is $0$; the time cost starting from planet $2$ is $1$; the time cost starting from planet $3$ is $2$; the time cost starting from planet $4$ is $0.8 \times 2 + 0.2 \times 3 = 2.2$. So the expected time is $\dfrac{0+1+2+2.2}{4}=1.3$. ### Constraints and Notes for Test Cases - For $30\%$ of the testdata, it is guaranteed that $1 \le n \le 2000$. - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^6$, $1 \le m \le n$, $0 < p < 1$. Round 14 Lanqiao Cup Software Contest Finals, C/C++ University Group B, Problem J. Translated by ChatGPT 5