CF 294E Shaass the Great【Tree】

将树的一条边移掉，然后将这条边重新连接两棵子树，使新树：两两点对的距离之和最小。

枚举删掉的边，对每种情况都计算一下，然后取最小值。

对于每种情况，假设左子树的两两点对和为S1，右子树为S2，子树结点个数分别为C1，C2，两个子树到树根的距离和分别为R1，R2，当前枚举的边的权值为w，则整棵树的代价为：

两棵子树的点对和+经过当前边的点对和

S1 + S2 + (C1 + C2)*w + C1*R2 + C2*R1

一棵树如果确定的话，S1和S2都是确定的，不确定的是R1和R2，因此只需要求出R1和R2的最小值。

f[i] 表示以i为根，其他所有结点到i的代价和。则R = min(f[i]), S = sigma(f[i]) / 2;

f[i]的值很容易通过两边遍历求出（具体看代码）。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define N 5003
const ll inf = 1ll<<60;

int n, s[N], size;
vector<pii> g[N];
ll d[N], ans, f[N], sum, res, s1, s2, r1, r2, c1, c2;
void dfs1(int now, int fa) {
    int u; ll w;
    s[now] = 1; f[now] = 0;
    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].first) != fa) {
            dfs1(u, now);
            s[now] += s[u];
            w = g[now][i].second;
            f[now] += f[u] + s[u]*w;
        }
}
void dfs2(int now, int fa) {
    int u; ll w;
    sum += f[now], res = min(res, f[now]);

    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].first) != fa) {
            w = g[now][i].second;
            f[u] = f[now] + w*(size-2*s[u]);
            dfs2(u, now);
        }
}
void work(int now, int fa) {
    int u; ll w;
    for (int i=0; i<g[now].size(); i++)
        if ((u = g[now][i].first) != fa) {
            dfs1(u, now); size = c1 = s[u]; sum = 0; res = inf;
            dfs2(u, now); s1 = sum/2; r1 = res;

            dfs1(now, u); size = c2 = s[now]; sum = 0; res = inf;
            dfs2(now, u); s2 = sum/2; r2 = res;

            w = g[now][i].second;
            ans = min(ans, s1+s2+c1*c2*w+c1*r2+c2*r1);

            work(u, now);
        }
}
int main() {
    scanf("%d", &n);
    for (int i=0; i<=n; i++) g[i].clear();

    for (int i=1, a, b, c; i<n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back(make_pair(b, c));
        g[b].push_back(make_pair(a, c));
    }

    ans = inf;
    work(1, 0);

    cout << ans << endl;
    return 0;
}