#P4359. Exp
Exp
题目描述
给出一个 个节点的无根树,以及一个点集 和一个初始值为 的计数器 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
其中,第 行表示从当前尚未处理的相邻节点集合 中等概率随机选择一个节点 nt。
求最终输出的 cnt 的期望。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,描述一条树边 。
接下来一行一个整数 ,表示集合 的大小。
接下来一行 个互不相同的整数,描述集合 。
输出格式
一行一个实数,描述答案。如果初始集合为空,直接输出 ,不执行 DFS。
当你的答案与标准答案的绝对误差不超过 时,视为你的答案正确。
输入输出样例
输入
3
1 2
2 3
2
1 3
输出
2.33333333
数据范围
,。