- 1#include 2#include 3#include 4#include 5 using namespace std;
- 6#define N 1000010 7 struct Edge {
- 8 int v,
- w,
- nxt;
- 9
- }
- edge[N * 2];
- 10 int head[N],
- tot,
- cur[N];
- long long sz[N];
- 11 12 void Add(int u, int v, int w) {
- 13 edge[tot] = (Edge) {
- v,
- w,
- head[u]
- };
- head[u] = tot++;
- 14 edge[tot] = (Edge) {
- u,
- w,
- head[v]
- };
- head[v] = tot++;
- 15
- }
- 16 17 void DFS(int u, int fa) {
- 18 sz[u] = 1;
- 19
- for (int i = head[u];~i; i = edge[i].nxt) {
- 20 int v = edge[i].v;
- 21
- if (v == fa) continue;
- 22 cur[v] = i;
- 23 DFS(v, u);
- 24 sz[u] += sz[v];
- 25
- }
- 26
- }
- 27 28 int main() {
- 29 int n;
- 30
- while (~scanf("%d", &n)) {
- 31 tot = 0;
- 32 memset(head, -1, sizeof(head));
- 33 memset(sz, 0, sizeof(sz));
- 34
- for (int i = 1; i < n; i++) {
- 35 int u,
- v,
- w;
- 36 scanf("%d%d%d", &u, &v, &w);
- 37 Add(u, v, w);
- 38
- }
- 39 DFS(1, -1);
- 40 long long ans = 0;
- 41
- for (int i = 2; i <= n; i++) {
- 42 ans += (long long) edge[cur[i]].w * abs(n - sz[i] - sz[i]);
- 43
- }
- 44 printf("%lld\n", ans);
- 45
- }
- 46
- return 0;
- 47
- }
来源: