TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4575
  • 题目
  • P4575点对游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    评测说明 : 1s,256m
    问题描述

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

    桑尼、露娜和斯塔三人轮流从树上所有未被占有的节点中选取一点,归为己有,轮流顺序为桑尼、露娜、斯塔、桑尼、露娜……。该选取过程直到树上所有点都被选取后结束。

    选完点后便可计算每人的得分。点对游戏中有m个幸运数,在某人占据的节点中,每有一对点的距离为某个幸运数,就得到一分。(树上两点之间的距离定义为两点之间的简单路径的边数)

    你的任务是,假设桑尼、露娜和斯塔每次选取时,都是从未被占有的节点中等概率选取一点,计算每人的期望得分。

     

    输入格式

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

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

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

    到n编号。

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

    输出格式

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

    样例输入 1

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

    样例输出 1

    0.60
    0.60
    0.00

    样例输入 2

    10 3
    3 4 2 
    1 2
    2 3
    1 4
    1 5
    2 6
    3 7
    1 8
    7 9
    8 10

    样例输出 2

    4.13
    2.07
    2.07


    来源  bzoj 4675