Expected Shortest Escape Time in a Galaxy Tree

In a distant galaxy there are \(n\) planets numbered from \(1\) to \(n\). These planets are connected by \(n-1\) undirected edges forming a tree with the root being planet \(1\). In preparation for an interstellar war, planet \(1\) is equipped with an escape portal.

Normally, a person on any planet can simply travel along the unique path towards the root by moving from the current planet to its parent. However, to help people travel faster, \(m\) of these planets are designated as jump board planets.

While moving towards the root, when a person is at some planet (including the starting planet), they may choose to attempt a jump. The jump is made to the first jump board planet on the current path to the root (excluding the current planet). The time cost for a jump is \(1\) unit (the same as moving to the parent).

Due to technical issues, every jump attempt has a probability \(p\) of failure. If a jump fails, the person instead moves to the parent (using \(1\) unit of time as usual) and the attempted jump board becomes disabled (i.e. it will no longer be treated as a jump board in the remainder of that journey).

Assuming that each person makes optimal decisions to minimize their expected travel time to the root and that a starting planet is chosen uniformly at random among all \(n\) planets, compute the expected minimum time (in time units) to reach planet \(1\).

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The first line contains three numbers: \(n\), \(m\) and \(p\) where \(n\) is the number of planets, \(m\) is the number of jump board planets, and \(p\) is the probability that a jump fails.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le n\)), indicating an undirected edge connecting planets \(u\) and \(v\). The tree is rooted at planet \(1\).

The last line contains \(m\) distinct integers, each representing a planet that is designated as a jump board.

outputFormat

Output a single floating‐point number representing the expected minimum time (in time units) required for a person, starting from a randomly chosen planet, to reach the root (planet \(1\)).

sample

3 1 0.5
1 2
1 3
2

0.666666667