codeforces 220 C. Game on Tree

题目链接

题解

对于 1节点一定要选的

发现对于每个节点，被覆盖切选中其节点的概率为祖先个数分之一，也就是深度分之一

代码

#include<cstdio>

#include<algorithm> 

const int maxn = 1000007;

struct node {

    int u,v,next;

} edge[maxn << 1] ;

int head[maxn],num = 0;

inline void add_edge(int u,int v) {

    edge[++ num].v = v;edge[num].next = head[u] ;head[u] = num;

}

int n;

double ans = 0;

double dep[maxn];

void dfs(int x,int fa) {

    ans += (1 / dep[x]);

    for(int i = head[x]; i; i = edge[i].next) {

        int v = edge[i].v;

        if(v == fa)continue;

           	dep[v] = dep[x] + 1.0;

        dfs(v,x);

    }

}

int main() {

    scanf("%d",&n);

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

           	scanf("%d%d",&u,&v);

        add_edge(u,v);add_edge(v,u) ;

    }

    dep[1] = 1;

    dfs(1,0);

    printf("%.10lf",ans);

    return 0;

}

巴特西

codeforces 220 C. Game on Tree

题目链接

题解

代码

最新文章

热门文章