Soluție HackerRank pentru Magic Number Tree, subdomeniul Probability, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Magic Number Tree
- Domeniu: Probability
- Limbaj: C++14
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
Cerință
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:
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 × n!) text{mod} (10^9+9). It is guaranteed that E_m × 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 × n!) text{mod} (10^9+9).
Constraints
* 1 ≤ n ≤ 5000
* 1 ≤ u_i,v_i ≤ n
* 1 ≤ w_i ≤ 10^9
Subtasks
* For 30% of the max score n ≤ 10
* For 60% of the max score n ≤ 400
Cod sursă
#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;
}