题解：P12007 【MX-X10-T3】[LSOT-4] 全国联赛？

Chiesl · 2025-03-31 17:25:59 · 题解

修改：2025.4.12，经提醒，修正状态转移方程中的一处笔误。

题意简述

有一张有 n 个节点，n - 1 条边的无向无环图（说白了就是一棵树，至于为什么后文会证明），已知 m 条边的起点，终点以及边权，还有剩下的 n - m - 1 条边的边权，求所有可能的树中任意两点的距离的和最小。

分析题目

我们将每个成员抽象成点，每个关系抽象成一条带权边，那我们的目标就是确定一张使得其中任意两个成员的距离的和最小的图。

不难发现，最后得到的目标图一定是一棵树，为什么呢？

首先，初始已经确定了 m 条边，我们发现将 n - m - 1 条边全部确定以后，一共有 n - 1 条边，并且根据题目题目中 如果有两个成员在最后无法配合，则认为不合法 以及 数据保证一定存在至少一种合法的方案 的表述，我们发现，最后形成的图一定是一个有着 n 个节点，n - 1 条边的无向连通图，也就是说其中一定没有环，有环则必不连通，那么需要得到的目标图其实也就是一棵可爱的树。

那么初始的输入里也不可能存在环。也就是说，我们会得到一颗颗小树，然后通过 n - m - 1 次“两树合并”得到最终的目标树。

解题思路

状态转移方程

我们不妨逆向思维一下，假设一些东西已经知道了，那就可以愉快的开始动态规划了 awa。

我们现在先考虑有两棵树，用一条权为 w 边将它们的根节点相连，组成的新树中，任意两点的距离的和为多少？

我们设 f_u 表示以 u 为根的子树中，所有节点到 u 的距离的和，F_u 表示以 u 该子树中任意两点的距离的和（假设已知，求法下文给出）。

设将要合并的两棵棵树的根节点分别为 u，v，节点数分别为 c_u，c_v，设新树的根节点为 root，那么连接 u，v 合并这两棵树后，新树的的 F_{root} 满足以下状态转移方程：

F_{root} = F_u + F_v + f_u \times c_v + f_v \times c_u + c_u \times c_v \times w

应该不难理解（知道你很急，怎么不写 f 的递推式？但是你先别急，下文介绍）。

从此处我们可以看出，先不考虑 w，因为两棵树的 c_u 与 c_v 是确定的，但是根节点的选择却会影响 f_u 与 f_v 的值，所以我们要将其最小化以取得最优，即选择最小的根节点使得树中所有点到根节点的距离的和最小，也就是树的重心。

假定 u，v 是树的重心，那么新的 root 一定是 u，v 中的一个，不妨假设 c_u > c_v（毕竟不满足可以交换），那么 root 一定是 u，通过选择 u 与 v 的 f 的不同的转移方程可以看出：

f_{root} = f_u + f_v + c_v \times w$ 选择 $u
f_{root} = f_u + f_v + c_u \times w$ 选择 $v

由于 c_u > c_v，所以上面那个肯定更优，所以上面的式子就是 f 的状态转移方程。

用这样不断地转移，最后只剩下一棵树那就是目标答案了。

此时读者可能要掀桌子了，你还没写许多关键的东西呢，怎么初始化、怎么安排合并的顺序以及 w，空写一个方程在这有什么用呢？请耐心看，非常感谢 qwq。

初始化

首先是 f 的初始化，其实一个小小的换根 DP 就解决了。那至于 F，其实是不用算出来的，准确的说，是不用把每个小小树（昵称）的 F 算出来，反正最后都是加到 ans 里的总量，所以算个总量即可，至于后面合并转移的时候，只需要将 ans 加上 f_u \times c_v + c_v \times c_u + c_u \times c_v \times w 就行了，稍稍改变状态转移方程，每次合并直接让 ans 增加，且只递推 f 就行了。

至于初始的 ans，它是这样算的：

ans = \frac{1}{2} \times \sum\limits_{i = 1} ^ n f_i

乘上 \frac{1}{2} 是因为算了两次，即 dist(u, v) 与 dist(v, u) 各算了一次。

合并顺序及边的安排

那么你肯定发现了，答案的值也会与合并的顺序以及选择的边有关，不能随便乱合并，那么究竟如何最优化呢？

首先，让越小的边承担越多的“行走”，即出现在两点间最短路的次数最多。

那么就是说最后合并两个剩下的最大的树时用最小的边权吗？当然不是！很显然首先是越早供合并用的边的承担的越多，其次才是供越大的两个树合并的边承担的越多。

为什么呢？你想，我们之前说了，新合成的树的重心会是原来那个树中点较多的一棵树的重心 u，那么此后假设有新的一棵树 T，其点数为 c_t 与该树合并，那么未选择的 v 及其子树都将经过合并用的边去与 T 上的每个节点联系，那么这条边就会被多经过 c_v \times c_t 次，此后也是如此。

读到此处，如果你觉得大彻大悟了，遍可开始自己着手写代码了，如果不知道具体如何设计程序可继续往下看。

程序设计

初始化 & 小小树的存储

前文所提的初始化很容易想到一遍循环遍历 n 个点去做换根 DP，只需要把每次经过的点标记下来就行，遇到之前已经经过的点就不做换根了，因为它包含在其他子树当中。这样就可以计算出初始时所有的 f_u 了（1 \le u \le n）。然后记录在每个小小树中最小的 f。实际程序实现时，只需要知道一个值就行，甚至不需要知道重心是哪个点。

这个过程，其实说白了就是求每个小小树的重心，然后用结构体储存下来该树所有点到重心的距离的和，放进优先队列里，以该树的节点数为关键字，后文要做“合并石子”。这一段的时间复杂度 O(n)，也就是换根 DP 的时间复杂度，即每个点只经过一次。

算初始 ans 时，有一个小细节，要取模，不然会喜提 WA。然后就是对 \sum\limits_{i = 1} ^ n f_i 取模 p 时，你会惊喜的发现有可能出现取模完变奇数的情况，此时直接除以二肯定炸了，还是难逃一 WA，所以将除以二变成乘以 500000004，这是 2 在模 10 ^ 9 + 7 意义下的逆元。

对于未确定的 n - m - 1 条边，从小到大排序即可，前文有讲述原因。

“合并石子”

我们发现，接下来的过程就像极了合并石子，每次取两个节点数最多的“石子”合并，刚好合并 n - m - 1 次后，就只剩下最后一棵我们所需要的大树了。

当然，可以不用优先队列，说白了就是一路从大合到小，比赛时脑子不清醒打了优先队列，而且好像确实蛮方便的 awa。

讲到这里，是不是可以自己实现了？如果实在还有不明白的地方就请观看代码吧！

虽然蒟蒻的码风并不喜人，但是还是添加了足够的注释以备神犇观看的 qwq。

代码如下

优先队列：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const ll p = 1e9 + 7, inv2 = 5e8 + 4;//模数与逆元
struct node {
    ll w;
    int nxt, to;
} edge[N << 1];
struct Node {
    ll f, cnt;//分别表示该树所有点到重心的距离和与该树的点数
    inline bool operator < (const Node &b) const {return cnt < b.cnt;}//重载运算符，以该树的点数为关键字
} a;//描述一棵树
bool vis[N];
priority_queue<Node> q;//默认大根堆
ll f[N], size[N], F[N], ans, w[N];
int n, m, head[N], tot, res, rt;
inline bool cmp (Node x, Node y) {return x.cnt > y.cnt;}
void add (int from, int to, ll w) {
    edge[++tot].nxt = head[from];
    edge[tot].to = to;
    edge[tot].w = w;
    head[from] = tot;
}//链式前向星应该都会吧？
void dfs1 (int u, int pa) {
    size[u] = 1, res++;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == pa) continue;
        dfs1(v, u), size[u] += size[v];
        f[u] += f[v] + size[v] * edge[i].w;
    }
}//第一次 dfs
void dfs2 (int u, int pa) {
    vis[u] = true;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == pa) continue;
        f[v] = f[u] + (res - 2 * size[v]) * edge[i].w;
        if (f[v] < a.f) a.f = f[v];
        dfs2(v, u);
    }
}//第二次 dfs，换根求重心应该都会吧？
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; i++) scanf("%d%d%d", &u, &v, &w), add(u, v, w), add(v, u, w);//无向边建俩
    for (int i = 1; i <= n - m - 1; i++) scanf("%lld", &w[i]);//输入
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            res = 0, dfs1(i, 0), a.f = f[i], dfs2(i, 0), a.cnt = res;//记录小小树
            q.push(a);//上文所述的具体实现
        }
    }
    for (int i = 1; i <= n; i++) ans = (ans + f[i]) % p;
    ans = (ans * inv2) % p;//初始答案
    Node u, v;
    sort(w, w + n - m);
    for (int i = 1; i <= n - m - 1; i++) {
        u = q.top(), q.pop(), v = q.top(), q.pop();/*取当前节点数最多的两个树出来
        （其实说白了就是从大合到小，一直合，也可以不用优先队列来实现，看个人，用优先队列其实不好
        可以按节点数从大到小排序以后直接和，比这个快很多，堆的操作也是有时间复杂度的）*/
        ans = (ans + u.f * v.cnt % p + v.f * u.cnt % p + u.cnt * v.cnt * w[i] % p) % p;//状态转移方程的程序实现
        u.f = ((u.f + v.cnt * w[i]) % p + v.f) % p, u.cnt = (u.cnt + v.cnt) % p;//新的树的各种信息更新
        q.push(u);//合并好的树继续放入堆中
    }//类似于合并石子
    printf("%lld", ans);
    return 0;
}

不使用优先队列：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const ll p = 1e9 + 7, inv2 = 5e8 + 4;//模数与逆元
struct node {
    ll w;
    int nxt, to;
} edge[N << 1];
struct Node {
    ll f, cnt;//分别表示该树所有点到重心的距离和与该树的点数
    inline bool operator < (const Node &b) const {return cnt > b.cnt;}//重载运算符，小于变大于，从大到小排序
} a[N];//描述一棵树
bool vis[N];
ll f[N], size[N], F[N], ans, w[N];
int n, m, head[N], tot, res, rt, cnt;
void add (int from, int to, ll w) {
    edge[++tot].nxt = head[from];
    edge[tot].to = to;
    edge[tot].w = w;
    head[from] = tot;
}//链式前向星应该都会吧？
void dfs1 (int u, int pa) {
    size[u] = 1, res++;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == pa) continue;
        dfs1(v, u), size[u] += size[v];
        f[u] += f[v] + size[v] * edge[i].w;
    }
}//第一次 dfs
void dfs2 (int u, int pa) {
    vis[u] = true;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == pa) continue;
        f[v] = f[u] + (res - 2 * size[v]) * edge[i].w;
        if (f[v] < a[cnt].f) a[cnt].f = f[v];

        dfs2(v, u);
    }
}//第二次 dfs，换根求重心应该都会吧？
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; i++) scanf("%d%d%d", &u, &v, &w), add(u, v, w), add(v, u, w);//无向边建俩
    for (int i = 1; i <= n - m - 1; i++) scanf("%lld", &w[i]);//输入
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) res = 0, dfs1(i, 0), a[++cnt].f = f[i], dfs2(i, 0), a[cnt].cnt = res;//记录小小树
    }
    for (int i = 1; i <= n; i++) ans = (ans + f[i]) % p;
    ans = (ans * inv2) % p;//初始答案
    Node u, v;
    sort(w, w + n - m), sort(a + 1, a + 1 + cnt);
    u = a[1];   
    for (int i = 2; i <= cnt; i++) {
        v = a[i], ans = (ans + u.f * v.cnt % p + v.f * u.cnt % p + u.cnt * v.cnt * w[i - 1] % p) % p;//状态转移方程的程序实现
        u.f = ((u.f + v.cnt * w[i - 1]) % p + v.f) % p, u.cnt = (u.cnt + v.cnt) % p;        
    }//正经实现
    printf("%lld", ans);
    return 0;
}

那么全文到这里就结束了，感谢审核管理员耐心看完，神犇幸苦了，求过 qwq。

如有不足，欢迎指出 awa。