1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define pr(x) cout << #x << ": " << x << "  " 
#define pl(x) cout << #x << ": " << x << endl;
typedef long long ll;
struct jibancanyang
{
    int n, m;
    vector<pair<int, int> > G[112345];
    int node[112345];
    ll ans = 0;
    void dfs(int cur, int far) {
        node[cur] = 1;
        for (int i = 0; i < int(G[cur].size()); ++i) {
            pair<int, int> nxt = G[cur][i];
            if (G[cur][i].first == far) continue;
            dfs(nxt.first, cur);
            node[cur] += node[nxt.first];
        }
        for (int i = 0; i < int(G[cur].size()); ++i) {
            if (G[cur][i].first == far) continue;
            int x = node[G[cur][i].first];
            ans += ll(n - x) * x * G[cur][i].second;
        }
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX