Editorial for Expected Pruning

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Let $I_v$ ~I_v~ be the indicator that vertex $v$ ~v~ is chosen directly at some step (rather than being deleted as part of an ancestor's subtree). Then $X = \sum_v I_v$ ~X = \sum_v I_v~, so

$E[X] = \sum_v \Pr(I_v = 1)$ ~E[X] = \sum_v \Pr(I_v = 1)~.

Vertex $v$ ~v~ is deleted as soon as any vertex on the unique path from the root to $v$ ~v~ (including $v$ ~v~ itself) is chosen. Until that happens, every vertex on that path is still present, and the process always chooses uniformly among remaining vertices. Therefore $v$ ~v~ is chosen directly if and only if, among $v$ ~v~ and its ancestors, $v$ ~v~ is the first one picked.

There are $\mathrm{depth}(v) + 1$ ~\mathrm{depth}(v) + 1~ vertices on that path (the root has depth $0$ ~0~), and they are symmetric, so

$\Pr(I_v = 1) = \frac{1}{\mathrm{depth}(v) + 1}$ .

The indicators are highly dependent: if the root is chosen first, then $I_v = 0$ ~I_v = 0~ for every other vertex. Linearity does not need independence. Summing the probabilities is $O(n)$ ~O(n)~ after a DFS or BFS that computes depths.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

long long modpow(long long a, long long e) {
    long long r = 1;
    a %= MOD;
    while (e) {
        if (e & 1) {
            r = r * a % MOD;
        }
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<int> > adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> depth(n + 1, 0);
    vector<int> parent(n + 1, 0);
    stack<int> st;
    st.push(1);
    parent[1] = -1;
    while (!st.empty()) {
        int v = st.top();
        st.pop();
        for (size_t i = 0; i < adj[v].size(); i++) {
            int to = adj[v][i];
            if (to == parent[v]) {
                continue;
            }
            parent[to] = v;
            depth[to] = depth[v] + 1;
            st.push(to);
        }
    }

    long long ans = 0;
    for (int v = 1; v <= n; v++) {
        ans += modpow(depth[v] + 1, MOD - 2);
        if (ans >= MOD) {
            ans -= MOD;
        }
    }
    cout << ans << "\n";
}

Comments

There are no comments at the moment.