1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 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 }