3112. [BZOJ 4675] 点对游戏

【题目描述】

桑尼、露娜和斯塔在玩点对游戏，这个游戏在一棵节点数为 n 的树上进行。桑尼、露娜和斯塔三人轮流从树上所有未被占有的节点中选取一点，归为己有，轮流顺序为桑尼、露娜、斯塔、桑尼、露娜……。该选取过程直到树上所有点都被选取后结束。选完点后便可计算每人的得分。点对游戏中有 m 个幸运数，在某人占据的节点中，每有一对点的距离为某个幸运数，就得到一分。（树上两点之间的距离定义为两点之间的简单路径的边数）你的任务是，假设桑尼、露娜和斯塔每次选取时，都是从未被占有的节点中等概率选取一点，计算每人的期望得分

【输入格式】

第一行两个整数 n、m，分别表示树的节点数和幸运数的数目。第二行 m 个互异正整数，表示 m 个幸运数。以下 n-1 行，每行两个整数 u、v，表示节点 u 和节点 v 之间有边。节点从 1到 n 编号。

【输出格式】

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

【样例输入】

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

【样例输出】

0.60
0.60
0.00

【提示】

对于数据点 1，n <= 1000；

对于数据点 2、3、4，第 i 个幸运数为 i；

对于数据点 5、6、7，n 为 3 的倍数；

对于所有数据点，3 <= n <= 50000，m <= 10，幸运数大小 <= n；