Codeforces 280C Game on Tree

佚名 / 2023-05-03 / 原文

设 \(p_i\) 为 \(i\) 涂色或不涂色，\(1\) 为涂，\(0\) 为不涂，答案即为 \(E[\sum_{i = 1}^n p_i]\)
然后转化一下柿子：\(\sum_{i=1}^nE[p_i]\)，这就很好求了，单独求每个点 \(E[p_i]\) 的值就行了

考虑对于 \(u\) 点，\(p_u = 1\)，即能被涂需要满足其祖先都比其晚涂色
假设现在有一个序列里面随机排列着这 \(n\) 个点，把 \(u\) 和其祖先都拿出来，则总共有 \(dep_u!\) 种方案，现在固定 \(u\) 排最前面，则方案数为 \((dep_u - 1)!\)，所以 \(E[p_u] = 1\times \frac{(dep_u - 1)!}{dep_u!} = \frac{1}{dep_u}\)

跑一个 dfs 就行了，时间复杂度 \(O(n)\)

无注释版本

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> to[N];
void add(int u, int v) {
    to[u].push_back(v);
    return ;
}
int dep[N];
double ans;
void dfs(int u, int fa) {
    ans += 1.0 / (dep[u] = dep[fa] + 1);
    for (int v : to[u]) {
        if (v == fa) {
            continue;
        }
        dfs(v, u);
    }
    return ;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    dfs(1, 0);
    printf("%.20lf", ans);
    return 0;
}