logo AlgoBeat OnlineJudge
登录 注册

#104675. [BZOJ 4675] 点对游戏

内存限制:256 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

桑尼、露娜和斯塔在玩点对游戏,这个游戏在一棵节点数为n的树上进行。

桑尼、露娜和斯塔三人轮流从树上所有未被占有的节点中选取一点,归为己有,

轮流顺序为桑尼、露娜、斯塔、桑尼、露娜……。该选取过程直到树上所有点都

被选取后结束。

选完点后便可计算每人的得分。点对游戏中有m个幸运数,在某人占据的节

点中,每有一对点的距离为某个幸运数,就得到一分。(树上两点之间的距离定

义为两点之间的简单路径的边数)

你的任务是,假设桑尼、露娜和斯塔每次选取时,都是从未被占有的节点中

等概率选取一点,计算每人的期望得分。

输入格式

第一行两个整数n、m,分别表示树的节点数和幸运数的数目。

第二行m个互异正整数,表示m个幸运数。

以下n-1行,每行两个整数u、v,表示节点u和节点v之间有边。节点从1

到n编号。

3 <= n <= 50000, m <= 10,幸运数大小 <= n

输出格式

三行实数,分别表示桑尼、露娜和斯塔的期望得分,保留两位小数。

样例

样例输入

5 2
1 3
1 2
1 5
2 3
2 4

样例输出

0.60
0.60
0.00