这是NOI11年题，你在逗我？
直接dfs就可以了，Linux下貌似不会爆栈。。。
1 /************************************************************** 2 Problem: 2435 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:5184 ms 7 Memory:76756 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 12 using namespace std; 13 typedef long long ll; 14 const int N = 1000005; 15 16 struct edge { 17 int next, to, v; 18 edge() {} 19 edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {} 20 } e[N << 1]; 21 22 struct tree_node { 23 int vis, sz; 24 } tr[N]; 25 26 int first[N], tot; 27 int n; 28 ll ans; 29 30 inline int read() { 31 int x = 0; 32 char ch = getchar(); 33 while (ch < '0' || '9' < ch) 34 ch = getchar(); 35 while ('0' <= ch && ch <= '9') { 36 x = x * 10 + ch - '0'; 37 ch = getchar(); 38 } 39 return x; 40 } 41 42 void Add_Edges(int x, int y, int z) { 43 e[++tot] = edge(first[x], y, z), first[x] = tot; 44 e[++tot] = edge(first[y], x, z), first[y] = tot; 45 } 46 47 inline int abs(int x) { 48 return x < 0 ? -x : x; 49 } 50 51 #define y e[x].to 52 void dfs(int p) { 53 int x; 54 tr[p].vis = tr[p].sz = 1; 55 for (x = first[p]; x; x = e[x].next) 56 if (!tr[y].vis) { 57 dfs(y); 58 tr[p].sz += tr[y].sz; 59 ans += 1ll * abs(n - (tr[y].sz << 1)) * e[x].v; 60 } 61 } 62 #undef y 63 64 int main() { 65 int i, x, y, z; 66 n = read(); 67 for (i = 1; i < n; ++i) { 68 x = read(), y = read(), z = read(); 69 Add_Edges(x, y, z); 70 } 71 dfs(1); 72 printf("%lld ", ans); 73 return 0; 74 }
(p.s. 貌似都找不到一个分类了。。。要死。。。就分在dfs序下好了)