Path Sum

1.cpp

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

#define endl '\n'
#define mp make_pair
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int max_n = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll M = 1e9;
const ll inf = 1e9;
const ld eps = 1e-9;

void setio(string name = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (!name.empty()) {
    freopen((name + ".txt").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  } else {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
  }
}
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int hdx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int hdy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
bool inside(int x, int y, int n, int m) {
  return x >= 0 && x < n && y >= 0 && y < m;
}
vector<pair<int, int>> adj[max_n];

int ans=0;

int dfs(int v, int par, int n) {
  int cnt = 1, c = 0;
  for (auto edge : adj[v]) {
    if(edge.first!=par) {
      c = dfs(edge.first, v, n);
      ans = (ans + c * 1LL * (n - c) * edge.second) % M;
      cnt += c;
    }
  }
  return cnt;
}

void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--;v--;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  dfs(0,-1,n);
  cout<<ans<<endl;
}

int32_t main() {
  setio();
  int tc = 1;
  auto start_time = clock();
 // cin >> tc;
  for (int t = 1; t <= tc; t++) {
    // cout << "case #" << t << ": ";
    solve();
  }
  auto end_time = clock();
#ifndef ONLINE_JUDGE
  cout << "Time taken:" << (double)(end_time - start_time) / CLOCKS_PER_SEC
       << "s" << endl;
#endif
  return 0;
}