HackerRank Probability – Magic Number Tree

Challenge: Magic Number Tree

Subdomeniu: Probability (probability)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464756770

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/james-tree/problem

Cerinta

James has a tree with $n$ nodes $n-1$ edges where the $i^{th}$ edge has a length, $w_i$. He wants to play a game involving $n$ moves. During each move, he performs the following steps:

* Randomly chooses some node $x_i$ from the tree. Each node has an equal probability of being chosen.
* Calculates the distance from node $x_i$ to each node reachable from $x_i$ using one or more edges.
* Deletes node $x_i$.

For example, the diagram below shows what happens when we choose a random node and delete it from the tree:

![image](https://s3.amazonaws.com/hr-challenge-images/0/1483093526-099fca06d4-magic11.png)

After $n$ moves, the tree is empty and the game ends.

James defines the magic number, $m$, as the sum of all numbers calculated in step $2$ of each move. Let $E_{m}$ be the [expected value](https://en.wikipedia.org/wiki/Expected_value) of $m$.

Give the tree's edges and their respective lengths, calculate and the print the value of $(E_{m} \times n!)\ \text{mod}\ (10^9+9)$. It is guaranteed that $E_{m} \times n!$ is an integer.


**Note**

Due to a bug in the system, you might see ``accepted`` verdict in this problem even if you don't pass all the test cases. Please ignore that verdict, only the score you get is important in the ranklist.

Input Format

The first line contains an integer, $n$, denoting the number of nodes. 	
Each of the $n-1$ subsequent lines contains three space-separated integers describing the respective values of $u_i$, $v_i$, and $w_i$, meaning that there is an edge of length $w_i$ connecting nodes $u_i$ and $v_i$.

Output Format

Print a single integer denoting the value of $(E_{m} \times n!)\ \text{mod}\ (10^9+9)$.

Constraints

* $1 \le n \le 5000$
* $1 \le u_i,v_i \le n$
* $1 \le w_i \le 10^9$

**Subtasks**

* For $30\%$ of the max score $n \le 10$
* For $60\%$ of the max score $n \le 400$

Cod sursa

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

static const long long MOD = 1000000009LL;

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

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

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

    vector<long long> inv(n + 1, 1);
    for (int i = 1; i <= n; ++i) inv[i] = modPow(i, MOD - 2);

    long long pairSum = 0; // sum over unordered pairs of 2*dist/(path_nodes)

    vector<int> parent(n + 1), hops(n + 1);
    vector<long long> dist(n + 1);

    for (int s = 1; s <= n; ++s) {
        // Iterative DFS from source s.
        vector<int> st;
        st.reserve(n);
        st.push_back(s);
        parent[s] = 0;
        hops[s] = 0;
        dist[s] = 0;

        while (!st.empty()) {
            int u = st.back();
            st.pop_back();

            for (const auto &e : g[u]) {
                int v = e.first;
                long long w = e.second;
                if (v == parent[u]) continue;
                parent[v] = u;
                hops[v] = hops[u] + 1;
                dist[v] = dist[u] + w;
                st.push_back(v);
            }
        }

        for (int v = s + 1; v <= n; ++v) {
            int pathNodes = hops[v] + 1;
            long long dmod = dist[v] % MOD;
            long long add = (__int128)2 * dmod % MOD;
            add = (__int128)add * inv[pathNodes] % MOD;
            pairSum += add;
            if (pairSum >= MOD) pairSum -= MOD;
        }
    }

    long long fact = 1;
    for (int i = 2; i <= n; ++i) fact = (__int128)fact * i % MOD;

    long long ans = (__int128)pairSum * fact % MOD;
    cout << ans << '\n';
    return 0;
}