CF280C

ZR补题计划

题意：

一棵有根树，每次选择一个未删除的节点，然后删除它和它的子树内的点，问期望删多少次可以把整个树删完

解析：

显然，通过题面，我们可以知道对于一个点对 $ (u,v) $ ，如果我们删除 $ u $ 那么 $ v $ 也一定会被删除, $ v $ 所在的子树的集合也一定会被删除。

因为期望的线性性，我们可以考虑一个节点被删除的期望次数。

并且我们可以知道，删除一个子树内的节点，只有可能删除这个节点，或者删除这个节点的一个祖先，然后实际上操作在这个点上的概率只有 $ \frac{1}{depth[i]} $ 。

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define LL long long

const int N = 1e5 + 100;

struct Edge {

    int to,from;

} e[N * 2];

int cnt,head[N],depth[N],n;

inline void add_edge(int x,int y) {

    e[++cnt].from = y;

    e[cnt].to = head[x];

    head[x] = cnt;

}

void dfs(int x,int fa,int deep) {

    depth[x] = deep;

    for(int i = head[x] ; i ; i = e[i].to) {

        int u = e[i].from;

        if(u == fa) continue;

        dfs(u,x,deep + 1);

    }

}

int main() {

    scanf("%d",&n);

    for(int i = 1 ; i < n ; i++) {

        int a,b;

        scanf("%d%d",&a,&b);

        add_edge(a,b);

        add_edge(b,a);

    }

    dfs(1,1,1);

    double ans = 0;

    for(int i = 1 ; i <= n ; i++)

        ans += 1.0 / depth[i];

    printf("%.10f \n",ans);

    //system("pause");

    return 0;

}

巴特西

CF280C

CF280C

题意：

解析：

CODE:

最新文章

热门文章