题意：
给出一棵n个点的树，每条边有边权。对这个树加边变成一个完全图。新加的边的权值为边上两点在树上的距离。求完全图上任意两点的最大流之和。
题解：
一共有C(n，2)个点对。假设当前求s到t之间的最大流，也就是最小割。那么割完之后会是2个连通块，且连通块内部是完全图。
因为是最小割，所以被割掉的边权和最小。即两个连通块内部的边权和最大。那么就会有一个连通块是孤立点，取s和t中到其余所有点距离小的作为孤立点。
问题变成了求每个点到其他所有点的距离。
dfs第一次求每个点到他所有儿子节点的距离，dfs第二次将剩余的距离更新。
最后排序统计答案。答案会爆ll所以要用类似大数的方法处理一下。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+;
const ll inf = 1e17;
int t, n, tot, cnt;
int u, v;
int num[N];
int head[N], to[N<<], nxt[N<<], w[N<<];
ll ans;
ll d[N];
void dfs(int u, int fa) {
num[u] = ;
d[u] = ;
for(int i = head[u]; ~i; i = nxt[i]) {
int v = to[i];
if(v == fa) continue;
dfs(v, u);
num[u] += num[v];
d[u] += d[v]+num[v]*w[i];
}
}
void re_dfs(int u, int fa) {
for(int i = head[u]; ~i; i = nxt[i]) {
int v = to[i];
if(v == fa) continue;
d[v] = d[u]+(n-*num[v])*w[i];
re_dfs(v, u);
}
}
int main() {
scanf("%d", &t);
for(int casee = ; casee <= t; casee++) {
scanf("%d", &n);
tot = ans = cnt = ;
memset(head, -, sizeof(int)*(n+));
for(int i = ; i < n; i++) {
scanf("%d%d", &u, &v);
to[++tot] = v; nxt[tot] = head[u]; head[u] = tot; scanf("%d", &w[tot]);
to[++tot] = u; nxt[tot] = head[v]; head[v] = tot; w[tot] = w[tot-];
}
dfs(, );
re_dfs(, );
sort(d+, d+n+);
for(int i = ; i <= n; i++) {
ans += d[i]*(n-i);
cnt += ans/inf;
ans %= inf;
}
if(cnt) printf("Case #%d: %d%017lld\n", casee, cnt, ans);
else printf("Case #%d: %lld\n", casee, ans);
}
}