#P4359. Exp

Exp

题目描述

给出一个 nn 个节点的无根树,以及一个点集 AA 和一个初始值为 00 的计数器 cnt。

现在随机选择一个点作为树根,然后执行如下 DFS 算法:

DFS(x)

1   if x ∈ A
2       then A ← A - {x}
3            if A = ∅
4                then print cnt
5                     exit
6   flag[x] ← TRUE
7   S ← the set of the nodes next to x
8   while S ≠ ∅
9       do nt ← a random element of S
10           S ← S - {nt}
11           if flag[nt] = FALSE
12               then cnt ← cnt + 1
13                    DFS(nt)
14                    cnt ← cnt + 1

其中,第 99 行表示从当前尚未处理的相邻节点集合 SS 中等概率随机选择一个节点 nt。

求最终输出的 cnt 的期望。

输入格式

第一行一个整数 nn。

接下来 n−1n-1 行,每行两个整数 x,yx,y,描述一条树边 (x,y)(x,y)。

接下来一行一个整数 mm,表示集合 AA 的大小。

接下来一行 mm 个互不相同的整数,描述集合 AA。

输出格式

一行一个实数,描述答案。如果初始集合为空,直接输出 00,不执行 DFS。

当你的答案与标准答案的绝对误差不超过 10−510^{-5} 时,视为你的答案正确。

输入输出样例

输入

3
1 2
2 3
2
1 3

输出

2.33333333

数据范围

1≤n≤1051\le n\le 10^5,0≤m≤n0\le m\le n。