Lang:G++
Edit12345678910111213141516171819202122232425262728293031#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;}}