题目：https://www.luogu.com.cn/problem/P2052
思路： 深度优先搜索dfs

include [HTML_REMOVED]

include [HTML_REMOVED]

include[HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
//众所周知，set能有序地维护同一类型的元素，但相同的元素只能出现一次。
const int N = 2e6 + 5;
//queue[HTML_REMOVED] que;
int h[N], e[N], w[N], ne[N], idx;
bool st[N];
//int cnt_out[N];
long long n,ans=0;
void add(int u, int v,int val) {
e[idx] = v;
w[idx] = val;
ne[idx] = h[u];
h[u] = idx;
}
int dfs(int x) {
st[x] = true;
int sum = 0;
for (int i = h[x]; i != -1; i = ne[i]) {
int v = e[i], val = w[i];
if (!st[v]) {
long long cnt = dfs(v);
sum += cnt;
ans += abs(n - cnt - cnt) * val;
}
}
return sum + 1;
}
int main() {
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i < n; i) {
int u, v, val;
cin >> u >> v >> val;
add(u, v,val), add(v, u,val);
}
dfs(1);
cout << ans << endl;
}