# CF280C Game on Tree

• 158通过
• 282提交
• 题目来源
• 评测方式 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类违反进行处理。