Compute the sum of pathes between any pairs of vertices in not oriented, connected graph with number of edges equal to number of vertices - 1.

sumAllPathGraph.cpp

/*
The problem is taken from https://www.e-olymp.com/en/problems/2157
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
lint mod = 1e9;

vector<list<int>> adj;
vector<bool> visited;
vector<lint> szSubtree;

lint comp(int v) {
    if (szSubtree[v] != -1) // actually should never happen
        return szSubtree[v];
    visited[v] = true;
    lint curSize = 1;
    for (int u : adj[v])
        if (!visited[u])
            curSize += comp(u);

    szSubtree[v] = curSize;
    return curSize;
}

int main(int, char**) {
    int n;
    cin >> n;
    adj.resize(n);
    visited.resize(n, false);
    szSubtree.resize(n, -1);

    vector< tuple<int, int, int> > price(n-1);
    for (int i = 0; i < n-1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        if (u > v)
            swap(u, v);
        price[i] = (make_tuple(u, v, w));
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    comp(0);

    lint sum = 0LL;
    for (auto& t : price) {
        lint szv = min(szSubtree[get<0>(t)], szSubtree[get<1>(t)]);
        sum = (sum + get<2>(t)*((szv) * (n - szv))%mod)%mod;
    }

    cout << sum << "\n";

    return 0;
}