Codeforces A. Game on Tree（期望dfs）

时间：2022-12-21 23:30:00

题目描述：

Game on Tree

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

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.

Output

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}\).

Examples

Input

Copy

21 2

Output

Copy

1.50000000000000000000

Input

Copy

31 21 3

Output

Copy

2.00000000000000000000

Note

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

思路：

题目是说在一棵树上删除节点，删除一个节点那么它的子树都要被删除，删除根节点1后就结束，删除的过程有个操作步数，不同的操作对应着操作步数。问这个操作步数的期望是多少。

刚开始：这怎么做？在画了几个图后发现好像有点意思，我想的是我现在从1步删完开始，假设一步删完，有一种操作，即直接删除根节点。我要两步删完，就要最后一步留着删根节点，第一步随便删一个节点。我要三步删完，最后一步删根节点，还有两步要删掉两个节点。于是以此列出了计算公式，然而之后我发现了问题，这个删两个节点是有顺序的啊，如果删了一个节点后它的字节点都不存在了，因此也不能删除了。于是我陷入了混乱中。

后来感觉到这个删除的顺序是跟节点本来的深度有关的，比这一步删的节点深度大的节点全部对步数不起作用，而另一方面，既然能删到这个节点，说明他的所有父结点都没有被删除。节点i对步数的贡献是1步，而能删到这个节点的概率是\(\frac{1}{depth[i]+1}\)（只要保证前面的没删过就行），因此最终的期望是\(\sum_i\frac{1}{depth[i]+1}\)。

代码的实现树的表示用到了链式前向星。如果有疑问可以看上一篇博客（嘻嘻）。

代码：

#include <iostream>
#include <iomanip>
using namespace std;
#define max_n 100005
int head[max_n];
struct edge
{
    int to;
    int next;
}e[max_n<<1];
int cnt = 0;
int d[max_n];
int n;
void add(int u,int v)
{
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
void dfs(int x,int from)
{
    for(int i = head[x];i;i=e[i].next)
    {
        if(e[i].to==from)
        {
            continue;
        }
        d[e[i].to] = d[x]+1;
        dfs(e[i].to,x);
    }
}
int main()
{
    cin >> n;
    for(int i = 1;i<n;i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    d[1] = 1;
    dfs(1,0);
    double ans = 0;
    for(int i = 1;i<=n;i++)
    {
        //cout << d[i] << endl;
        ans = ans+1.0/d[i];
    }
    cout.setf(ios_base::fixed,ios_base::floatfield);
    cout << setprecision(20) << ans << endl;
    return 0;
}

参考文章：

LeTri，Codeforces 280C. Game on Tree，https://www.cnblogs.com/LeTri/p/9157166.html
标签：

相关文章