Codeforces 280C Game on Tree 期望

Game on Tree

这种题好像在wannfly训练营讲过， 我怎么又不会写啦， 我好菜啊啊啊。

我们按每个点算贡献， 一个点有贡献就说明它是被选中的点， 那么它被选中的概率就为1 / depth

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int n;

vector<int> G[N];

double ans;

void dfs(int u, int fa, int depth) {

    ans += 1.0 / depth;

    for(int v : G[u])

        if(v != fa) dfs(v, u, depth + );

}

int main() {

    scanf("%d", &n);

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

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

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(, , );

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

    return ;

}

/*

*/