Editorial for Expected Pruning

Use this editorial only when stuck, and do not 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$ be the indicator that vertex $v$ is chosen directly at some step (rather than being deleted as part of an ancestor's subtree). Then $X = \sum_v I_v$ , so

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

Vertex $v$ is deleted as soon as any vertex on the unique path from the root to $v$ (including $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$ is chosen directly if and only if, among $v$ and its ancestors, $v$ is the first one picked.

There are $\mathrm{depth}(v) + 1$ vertices on that path (the root has depth $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$ for every other vertex. Linearity does not need independence. Summing the probabilities is $O(n)$ after a DFS or BFS that computes depths.

Solution (C++)

Code 1

#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";
}

Comments0

No comments yet

Be the first to comment.

Editorial for Expected Pruning

Approach

Solution (C++)

Comments0

New comment