BZPRO
#4675. 点对游戏
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
桑尼、露娜和斯塔在玩点对游戏，这个游戏在一棵节点数为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
数据范围与提示
BZPRO