CF280C Game on Tree

    • 158通过
    • 282提交
  • 题目来源 CodeForces 280C
  • 评测方式 RemoteJudge
  • 标签 数论,数学 期望
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    • 题目描述

    给出一棵树,每次随机等概率选择一未染黑的点,将它及其子树染黑。问期望多少次操作可以将树全部染黑。

    • 输入格式

    第一行为一个整数$n$,描述这棵树有$n$个节点。

    接下来$n-1$行,每行两个整数$a_i$和$b_i$,描述这个树的其中一条边的起点和终点的编号分别为$a_i$和$b_i$。

    • 输出格式

    输出一个实数,为描述的期望。

    你的答案与标准答案若相差不超过$10^{-6}$,则你的答案就是正确的。

    • 样例解释

    在第一个示例中,有两个案例。

    一个是直接删除根,另一个是在一个步骤后删除根。 因此,预期的步骤如下:

    $1×(1/2)+2×(1/2)=1.5 $

    在第二个样本中,情况变得更加复杂。有两种情况可以减少到第一个样本,一个案例立即被清理。

    因此,预期的步骤如下:

    $1×(1/3)+(1+1.5)×(2/3)=(1/3)+(5/3)=2$

    • 数据规模与约定

    保证 $1≤n≤10^5$。 $ 1<=a_{i},b_{i}<=n$ 且 $ a_{i}≠b_{i}$

    感谢@feicx 提供的翻译

    题目描述

    Momiji has got a rooted tree, consisting of $ n $ nodes. The tree nodes are numbered by integers from $ 1 $ to $ n $ . The root has number $ 1 $ . Momiji decided to play a game on this tree.

    The game consists of several steps. On each step, Momiji chooses one of the remaining tree nodes (let's denote it by $ v $ ) and removes all the subtree nodes with the root in node $ v $ from the tree. Node $ v $ gets deleted as well. The game finishes when the tree has no nodes left. In other words, the game finishes after the step that chooses the node number $ 1 $ .

    Each time Momiji chooses a new node uniformly among all the remaining nodes. Your task is to find the expectation of the number of steps in the described game.

    输入输出格式

    输入格式:

    The first line contains integer $ n $ $ (1<=n<=10^{5}) $ — the number of nodes in the tree. The next $ n-1 $ lines contain the tree edges. The $ i $ -th line contains integers $ a_{i} $ , $ b_{i} $ $ (1<=a_{i},b_{i}<=n; a_{i}≠b_{i}) $ — the numbers of the nodes that are connected by the $ i $ -th edge.

    It is guaranteed that the given graph is a tree.

    输出格式:

    Print a single real number — the expectation of the number of steps in the described game.

    The answer will be considered correct if the absolute or relative error doesn't exceed $ 10^{-6} $ .

    输入输出样例

    输入样例#1: 复制
    2
    1 2
    
    输出样例#1: 复制
    1.50000000000000000000
    
    输入样例#2: 复制
    3
    1 2
    1 3
    
    输出样例#2: 复制
    2.00000000000000000000
    

    说明

    In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are:

    $ 1×(1/2)+2×(1/2)=1.5 $ In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are:

    $ 1×(1/3)+(1+1.5)×(2/3)=(1/3)+(5/3)=2 $

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。