P1131 [ZJOI2007] Time Synchronization - Luogu Solution • MuXinCG's Blog

好久没写算法题的分析了，今天来写一下

在以激发器为根的树上，只能给某条边的传输时间增加整数单位，要求所有”终止节点”（叶子）同时收到信号，求最少操作次数。本文给出一次 $O(N)$ 的树形 DP。

题目描述#

小 Q 在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字 $1,2,3\cdots$ 进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。

在电路板上存在一个特殊的元件称为”激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激励电流将到达一些”终止节点”――接收激励电流之后不再转发的节点。

激励电流在导线上的传播是需要花费时间的，对于每条边 $e$ ，激励电流通过它需要的时间为 $t_e$ ，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个”终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小 Q 有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小 Q 最少使用多少次道具才可使得所有的”终止节点”时态同步？

输入格式#

第一行包含一个正整数 $N$ ，表示电路板中节点的个数。

第二行包含一个整数 $S$ ，为该电路板的激发器的编号。

接下来 $N-1$ 行，每行三个整数 $a,b,t$ 。表示该条导线连接节点 $a$ 与节点 $b$ ，且激励电流通过这条导线需要 $t$ 个单位时间。

输出格式#

仅包含一个整数 $V$ ，为小 Q 最少使用的道具次数。

输入输出样例#

输入：

plaintext

输出：

plaintext

数据范围#

对于 $40\%$ 的数据， $1 \le N \le 1000$ 。
对于 $100\%$ 的数据， $1 \le N \le 5 \times 10^5$ 。
对于所有的数据， $1 \le t_e \le 10^6$ 。

思路分析#

题目给定了一棵以激发器 $S$ 为根的带权无根树，要求所有叶子（终止节点）从根出发收到信号的时间一致。注意一个非常关键的限制：道具只能增加边权，不能减少。也就是说，对每个子树的根 $u$ ，我们必须把 $u$ 到子树内每个叶子的路径长度全部”拉齐”到当前子树内最长的那条路径。这就告诉我们，最优策略是从下往上贪心地对齐，整个过程具有典型的子问题独立性，可以用树形 DP 解决。

状态定义#

设 $f[u]$ 表示以 $u$ 为根的子树内，从 $u$ 到任意叶子的最长路径长度（同时也是子树同步完成后所有叶子到 $u$ 的距离）。

转移与代价计算#

设 $u$ 有若干孩子 $v_1, v_2, \ldots, v_k$ ，对应边权分别为 $w_1, w_2, \ldots, w_k$ 。

经过 $v_i$ 这条分支到达叶子的最长路径长度为 $f[v_i] + w_i$ 。要让所有分支同步到达 $u$ ，必须将每个分支的长度都抬高到

f[u] = \max_{1 \le i \le k} (f[v_i] + w_i)

那么在 $u$ 处新增的总代价为：

\Delta_u = \sum_{i=1}^{k} \big( f[u] - f[v_i] - w_i \big)

最终答案为所有非叶子节点处的 $\Delta_u$ 之和。

为什么把代价加在边 $(u, v_i)$ 上是最优的？#

不能减少、只能增加边权这一约束，决定了我们必须以”最长分支”作为基准。一旦 $v_i$ 的子树内部已同步好，无论把抬高量加在 $u$ 到 $v_i$ 的边上、还是 $v_i$ 子树里的某条边上，对子树内部的同步性都没有任何影响（因为相同的常数会被加到 $v_i$ 子树的所有叶子距离上）。所以，把抬高量直接加在 $u \to v_i$ 这条最近的边上，是最简洁、且与正确性等价的方案，能保证我们不会重复计算或破坏已对齐的结构。

用样例验证#

样例中根为 $1$ ，叶子为 $2,3$ ，边权分别为 $1$ 和 $3$ ：

$f[2] = f[3] = 0$
$f[1] = \max(0 + 1, 0 + 3) = 3$
$\Delta_1 = (3 - 0 - 1) + (3 - 0 - 3) = 2 + 0 = 2$

答案为 $2$ ，与样例输出一致。

实现细节#

$N$ 可达 $5 \times 10^5$ ， $t_e$ 最大 $10^6$ ，单条路径长度最坏到 $5 \times 10^{11}$ 级别，所以 $f[u]$ 与最终答案 必须使用 long long。
数据较大，建议关闭同步流并使用邻接表存图。
树最深可能达到 $N$ （链状），递归 DFS 可能爆栈，竞赛中可手动开大栈或改写为迭代版本（下方提供了递归版本，必要时可改写）。

代码实现#

// Problem: P1131 [ZJOI2007] 时态同步
// URL: https://www.luogu.com.cn/problem/P1131
// Tags: Tree DP
//    ███╗   ███╗██╗   ██╗██╗  ██╗██╗███╗   ██╗ ██████╗ ██████╗ 
//    ████╗ ████║██║   ██║╚██╗██╔╝██║████╗  ██║██╔════╝██╔════╝ 
//    ██╔████╔██║██║   ██║ ╚███╔╝ ██║██╔██╗ ██║██║     ██║  ███╗
//    ██║╚██╔╝██║██║   ██║ ██╔██╗ ██║██║╚██╗██║██║     ██║   ██║
//    ██║ ╚═╝ ██║╚██████╔╝██╔╝ ██╗██║██║ ╚████║╚██████╗╚██████╔╝
//    ╚═╝     ╚═╝ ╚═════╝ ╚═╝  ╚═╝╚═╝╚═╝  ╚═══╝ ╚═════╝ ╚═════╝ 

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 10;

int N, S;
struct Edge {
    int to, w;
};
vector<Edge> g[MAXN];
long long f[MAXN];   // f[u]: 以 u 为根的子树中, u 到叶子的最大路径长度
long long ans = 0;   // 累计的道具使用次数

void dfs(int u, int parent) {
    f[u] = 0;
    // 第一遍: 求出 f[u]
    for (auto &e : g[u]) {
        if (e.to == parent) continue;
        dfs(e.to, u);
        f[u] = max(f[u], f[e.to] + (long long)e.w);
    }
    // 第二遍: 在 u 处把每个分支都拉齐到 f[u]
    for (auto &e : g[u]) {
        if (e.to == parent) continue;
        ans += f[u] - f[e.to] - e.w;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> S;
    for (int i = 1; i < N; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        g[a].push_back({b, t});
        g[b].push_back({a, t});
    }

    dfs(S, 0);

    cout << ans << '\n';
    return 0;
}

cpp

复杂度分析#

时间复杂度： $O(N)$ 。每个节点在 DFS 中被访问一次，每条边在两遍循环里各被遍历常数次，整体线性。
空间复杂度： $O(N)$ 。邻接表存图占 $O(N)$ ， $f$ 数组占 $O(N)$ ，DFS 递归栈最坏达 $O(N)$ （链状树时）。

P1131 [ZJOI2007] Time Synchronization - Luogu Solution