2026CSP-S第二轮复赛模拟赛题解

Yuilice

2026-10-21 10:51:44

发布于：浙江

230阅读

0回复

0点赞

题号	题目	完整算法	时间复杂度	空间复杂度
A	灯塔巡航	排序、二分、动态规划	$O(n\log n)$	$O(n)$
B	优惠通道	分层状态图、Dijkstra	$O((n+m)\log(n+m))$	$O(n+m)$
C	区间能量	懒标记线段树	$O(n+q\log n)$	$O(n)$
D	树上信标	换根动态规划	$O(n)$	$O(n)$

A. 灯塔巡航

解题思路

题意分析

记任务数量为 $n$ ，第 $i$ 个任务的时间区间为 $[l_i,r_i)$ 、能量为 $v_i$ 。首先考虑按时间顺序执行任务。若一个方案中的任务互不冲突，它们就能按结束时刻从小到大排列。于是先将所有任务按照结束时刻排序，之后只需研究排序后的任务前缀。下文的任务编号均指排序后的编号。

任务能量不同时，只看某个局部条件无法决定是否选择任务。单个任务能量较高，也可能挤占其他任务的执行时间，导致总能量更低。因此，需要同时比较“选择当前任务”和“跳过当前任务”两类方案。

定义 $\mathrm{dp}[i]$ 为只考虑前 $i$ 个任务时，能够获得的最大能量。这里“考虑”表示这些任务允许被选择，并不要求全部执行。没有任务时， $\mathrm{dp}[0]=0$ 。

对第 $i$ 个任务分类讨论。如果跳过它，其他任务都在前 $i-1$ 个任务中，最优收益就是 $\mathrm{dp}[i-1]$ 。

如果选择它，之前执行的任务必须在时刻 $l_i$ 或更早结束，即满足 $r_j\le l_i$ 。由于结束时刻已经有序，这些任务恰好组成一个前缀。令 $p_i$ 为前 $i-1$ 个任务中满足 $r_j\le l_i$ 的任务数量，那么可以从前 $p_i$ 个任务中选出最优方案，再接上当前任务，获得 $\mathrm{dp}[p_i]+v_i$ 点能量。若没有任务能衔接，便有 $p_i=0$ 。

因此状态转移为

$\mathrm{dp}[i]=\max\bigl(\mathrm{dp}[i-1],\ \mathrm{dp}[p_i]+v_i\bigr).$

这里可以将前 $p_i$ 个任务的任意合法方案直接接到任务 $i$ 之前：该前缀内每个任务的结束时刻都不大于 $l_i$ ，所以整个方案必然已在当前任务开始前完成。

现在只剩下如何快速求出 $p_i$ 。若逐个向前扫描，每个任务最多检查 $n$ 个前驱，总计需要 $O(n^2)$ 时间。结束时刻有序，可以使用二分查找，将一次查询缩短到 $O(\log n)$ 。

具体来说，upper_bound 找到第一个严格大于 $l_i$ 的结束时刻，它前面的元素数量就是 $p_i$ 。必须保留结束时刻恰好等于 $l_i$ 的任务，才能符合半开区间的衔接规则。参考代码中的任务数组从下标 $0$ 开始，而动态规划数组从下标 $1$ 开始；二分查找得到的是可用前缀的长度，可以直接作为动态规划下标。

最终， $\mathrm{dp}[n]$ 就是所有任务的最优答案。

部分分说明：

测试点 $1\sim5$ （ $n\le1000$ ， $r_i\le10^4$ ， $v_i\le10^3$ ）：按结束时刻排序，使用同样的动态规划，但通过逐个扫描前面的任务求出 $p_i$ 。时间复杂度为 $O(n^2)$ ，可以处理这一组数据。
测试点 $6\sim10$ （所有任务满足 $v_i=V$ ）：总能量等于选择的任务数乘以 $V$ ，转为最大化互不冲突的任务数量。按结束时刻排序，每次选择最早结束且能够衔接的任务。最早结束的选择会给后续任务留下尽可能多的时间，因此区间选择贪心可以处理这一组数据。
测试点 $11\sim15$ （ $r_i\le10^6$ ）：可以按整数时刻做动态规划。令 $f[t]$ 表示所有选中任务不晚于时刻 $t$ 完成时能获得的最大能量，将任务按结束时刻分组，计算 $f[t]=\max\bigl(f[t-1],\ \max_{r_i=t}(f[l_i]+v_i)\bigr)$ ，初始化 $f[0]=0$ 。由于 $l_i<r_i$ ，转移时需要的状态均已算出。令 $T=\max r_i$ ，时间与空间复杂度均可控制在 $O(n+T)$ 。
测试点 $16\sim20$ （完整数据范围）：结束时刻可达 $10^9$ ，使用按结束时刻排序、二分查找前驱的动态规划，时间复杂度为 $O(n\log n)$ 。这一做法也适用于前面的全部测试点。

实现步骤

读入所有任务，按照结束时刻从小到大排序，并保存排序后的结束时刻数组。
建立长度为 $n+1$ 的动态规划数组，将 $\mathrm{dp}[0]$ 初始化为 $0$ 。
按顺序处理第 $i$ 个任务，在前 $i-1$ 个结束时刻中使用 upper_bound 求出 $p_i$ 。
按照转移式比较跳过和选择当前任务的收益，得到 $\mathrm{dp}[i]$ 。
输出 $\mathrm{dp}[n]$ 。

正确性证明

对考虑的任务数量 $i$ 进行归纳，证明 $\mathrm{dp}[i]$ 等于前 $i$ 个任务的最优收益。

当 $i=0$ 时，没有任务可以执行，最大收益为 $0$ ，与初始化一致。

假设所有下标小于 $i$ 的状态都已正确求出。考察前 $i$ 个任务的任意最优方案。

若方案没有选择第 $i$ 个任务，它完全由前 $i-1$ 个任务组成，收益至多为 $\mathrm{dp}[i-1]$ ；由归纳假设，该收益也确实能够达到。

若方案选择了第 $i$ 个任务，因为第 $i$ 个任务的结束时刻在前 $i$ 个任务中最晚，且每个任务都有 $l_j<r_j$ ，其他任务不可能安排在它之后，只能在它开始前结束。这些任务均满足 $r_j\le l_i$ ，属于前 $p_i$ 个任务，所以它们的总收益至多为 $\mathrm{dp}[p_i]$ 。反过来，前 $p_i$ 个任务的最优方案能够合法地接上第 $i$ 个任务，达到 $\mathrm{dp}[p_i]+v_i$ 。

两类方案覆盖了所有可能，分别取各类最大收益再取最大值，就得到正确的 $\mathrm{dp}[i]$ 。由数学归纳法，最终输出的 $\mathrm{dp}[n]$ 正确。

复杂度分析

排序需要 $O(n\log n)$ 时间，每个任务进行一次 $O(\log n)$ 的二分查找与一次常数时间的转移，总时间复杂度为 $O(n\log n)$ 。任务数组、结束时刻数组和动态规划数组共占用 $O(n)$ 空间。

参考代码

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

struct Task {
    int l, r;
    long long v;
};

int main() {
    freopen("lantern.in", "r", stdin);
    freopen("lantern.out", "w", stdout);

    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<Task> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%lld", &a[i].l, &a[i].r, &a[i].v);
    }

    // 结束时间有序后，可衔接的任务组成一个前缀。
    sort(a.begin(), a.end(), [](Task x, Task y) {
        if (x.r != y.r) return x.r < y.r;
        return x.l < y.l;
    });

    vector<int> r(n);
    for (int i = 0; i < n; i++) r[i] = a[i].r;

    // dp[i] 表示只考虑排序后的前 i 个任务时的最大能量。
    vector<long long> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        Task t = a[i - 1];
        // upper_bound 保留 r <= l 的任务，p 同时是可用前缀长度。
        int p = upper_bound(r.begin(), r.begin() + i - 1, t.l)
                - r.begin();
        dp[i] = max(dp[i - 1], dp[p] + t.v);
    }

    printf("%lld\n", dp[n]);
    return 0;
}

B. 优惠通道

解题思路

题意分析

设原图有 $n$ 个路口和 $m$ 条双向道路，起点为 $1$ ，终点为 $n$ 。普通最短路只记录到达每个路口的最小时间。但在本题中，到达同一个路口的两条路线，还可能具有不同的优惠券使用情况。

例如，到达某个路口时，一条路线耗时较少，但优惠券已经使用；另一条路线耗时略多，却保留着优惠券。若后面有一条耗时很大的道路，第二种状态就可能得到更好的最终结果。因此，不能只保留一个最短距离，需要将“优惠券是否已经使用”也加入状态。

将状态记为 $(u,k)$ ，其中 $u$ 是当前路口， $k=0$ 表示优惠券尚未使用， $k=1$ 表示已经使用。定义 $\mathrm{d}[u][k]$ 为从起点出发，到达这一状态的最小耗时。初始时人在路口 $1$ ，优惠券尚未使用，所以

$\mathrm{d}[1][0]=0,$

其余状态暂设为无穷大。

现在考虑从路口 $u$ 沿一条权值为 $w$ 的道路走到路口 $v$ 。如果正常通行，优惠券的使用情况保持不变，状态转移为

$(u,k)\longrightarrow(v,k),\qquad \text{费用为 }w.$

如果优惠券还未使用，还可以在这次经过道路时使用它，使当前费用变为 $0$ ，状态转移为

$(u,0)\longrightarrow(v,1),\qquad \text{费用为 }0.$

已经使用优惠券的状态只允许继续正常通行。这样，任意一条状态转移路径最多只会发生一次从未使用到已使用的变化，也就准确地限制了优惠券的使用次数。

可以将每个原图路口拆成两个状态。这个状态图共有 $2n$ 个点；原图每条无向道路对应两种方向，每个方向有两条正常通行的状态边，以及一条使用优惠券的状态边，因此状态边数为 $6m$ 。实际编程时保存原图邻接表，在遍历道路时进行上述转移即可。

所有状态边的权值都非负，包括使用优惠券产生的零权边，因此可以使用 Dijkstra 算法。用小根堆维护当前距离最小的待处理状态，每次取出后沿原图相邻道路进行松弛。一个状态的距离被改小时，将新的记录放入堆中；之后若取出的记录已经过期，就直接跳过。

到达终点时，优惠券可以已经使用，也可以仍然保留，所以答案为

$\min\bigl(\mathrm{d}[n][0],\ \mathrm{d}[n][1]\bigr).$

若两者都是无穷大，终点不可达，输出 -1。特别地，当 $n=1$ 时，已经位于终点，可以不经过道路、不使用优惠券，正确答案为 $0$ ；对两个状态取最小值会自然地覆盖这种情况。

部分分说明：

测试点 $1\sim5$ （ $n,m\le1000$ ）：仍然使用两个优惠券状态，但采用朴素 Dijkstra。每轮扫描全部 $2n$ 个状态，选出尚未确定且距离最小的状态，再通过邻接表进行松弛。时间复杂度为 $O(n^2+m)$ ，可以处理这一组数据。
测试点 $6\sim10$ （ $n,m\le2\times10^5$ ，每条道路的权值均为 $W$ ）：一条经过 $k$ 条道路的路线，最小耗时是 $\max(k-1,0)W$ 。这一值随 $k$ 增大而不减，因此对原图运行 BFS，求出从 $1$ 到 $n$ 最少需要经过多少条道路即可。若不可达输出 -1，否则用该公式计算答案，时间复杂度为 $O(n+m)$ 。
测试点 $11\sim20$ （完整数据范围）：使用状态扩展和堆优化 Dijkstra。该做法适用于所有测试点。

实现步骤

读入道路，按照双向道路建立邻接表。
将所有距离初始化为无穷大，令 $\mathrm{d}[1][0]=0$ ，把状态 $(1,0)$ 及距离 $0$ 放入小根堆。
取出距离最小的状态；如果堆中的距离与当前记录不一致，跳过这条过期记录。
遍历相邻道路，尝试正常通行，更新相同优惠券状态下的距离。
如果当前优惠券尚未使用，再尝试免费经过该道路，更新已使用优惠券的状态。每次成功更新后，将新记录放入堆。
堆为空后，取终点两个状态距离的最小值；不可达时输出 -1，否则输出这一最小值。

正确性证明

首先证明原问题中的合法路线与状态图中的路径相互对应，并且总费用相同。

给定一条至多使用一次优惠券的合法路线，从状态 $(1,0)$ 开始。正常经过道路时，走状态图中费用为原边权且优惠券状态不变的边；若在某次经过道路时使用优惠券，就走从未使用状态到已使用状态的零权边。这样能够到达终点的某个状态，且每次经过道路的计费方式与原路线一致。

反过来，给定一条从 $(1,0)$ 出发的状态图路径，将每次转移还原为原图中的道路经过。状态图只允许从未使用状态转为已使用状态，不能反向恢复，因此路径至多包含一次免费经过。还原后得到合法路线，且费用保持不变。

于是，题目要求的最小耗时等于状态图中从 $(1,0)$ 到 $(n,0)$ 、 $(n,1)$ 的最短距离的较小值。

状态图所有边的权值均非负。Dijkstra 每次选择当前距离最小的未确定状态时，如果存在更短路径，则该路径上第一个未确定状态的前驱已经被处理过，相应松弛会给出不大于这条更短路径前缀的距离。由于之后的边权非负，这会与当前选出的距离最小性矛盾。因此每次确定的距离正确，所有可达状态的最短距离都能正确求出。

最终取终点两个状态的较小距离，恰好涵盖使用和不使用优惠券的全部合法路线；两者均不可达时输出 -1。因此算法正确。

复杂度分析

状态图有 $2n$ 个状态和 $6m$ 条有向状态边。邻接表建图需要 $O(n+m)$ 时间，堆优化 Dijkstra 的时间复杂度为 $O((n+m)\log(n+m))$ ，距离、邻接表和堆共占用 $O(n+m)$ 空间。这里用 $\log(n+m)$ 计入堆中可能保留的过期记录。

参考代码

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

struct Edge {
    int to;
    long long w;
};

int main() {
    freopen("coupon.in", "r", stdin);
    freopen("coupon.out", "w", stdout);

    int n, m;
    if (scanf("%d%d", &n, &m) != 2) return 0;
    vector<vector<Edge>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        scanf("%d%d%lld", &u, &v, &w);
        // 道路可以双向通行。
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    long long inf = (1LL << 62);
    vector<array<long long, 2>> d(n + 1, {inf, inf});
    using T = tuple<long long, int, int>;
    priority_queue<T, vector<T>, greater<T>> q;

    // 出发时还没有使用优惠券。
    d[1][0] = 0;
    q.push({0, 1, 0});

    while (!q.empty()) {
        auto [du, u, k] = q.top();
        q.pop();
        // 同一状态可能多次入堆，跳过已经失效的记录。
        if (du != d[u][k]) continue;

        for (Edge e : g[u]) {
            // 正常通行，优惠券的使用状态不变。
            if (d[e.to][k] > du + e.w) {
                d[e.to][k] = du + e.w;
                q.push({d[e.to][k], e.to, k});
            }

            // 尚未使用优惠券时，可以免除本次经过的费用。
            if (k == 0 && d[e.to][1] > du) {
                d[e.to][1] = du;
                q.push({du, e.to, 1});
            }
        }
    }

    // 至多使用一次，允许完全不使用；n = 1 时答案也是 0。
    long long ans = min(d[n][0], d[n][1]);
    if (ans == inf) printf("-1\n");
    else printf("%lld\n", ans);
    return 0;
}

C. 区间能量

解题思路

题意分析

设数组长度为 $n$ ，操作次数为 $q$ ，数组初始全为 $0$ 。

从直接维护数组开始。 对区间 $[l,r]$ 加上 $v$ 时，逐个修改数组中的元素；查询时，逐个累加区间中的元素。每次操作最多访问 $n$ 个位置，总时间复杂度为 $O(nq)$ 。当 $n,q\le 1000$ 时，这个方法可以完成计算；当两者都达到 $2\times 10^5$ 时，需要更快的区间维护方法。

静态数组可以用前缀和快速查询，但本题修改与查询交替出现。一次区间修改会影响多个前缀和，逐个重新维护仍可能花费 $O(n)$ 时间。我们需要同时加速区间修改和区间查询。

用线段树维护区间和。 线段树根节点管理 $[1,n]$ ，每个非叶节点将所管理的区间 $[L,R]$ 分成 $[L,M]$ 与 $[M+1,R]$ ，其中 $M=\lfloor(L+R)/2\rfloor$ 。节点 $p$ 用 $\mathrm{sum}_p$ 保存其区间的元素和。若左右子节点都已包含应有的修改，父节点的和等于左右子节点的和：

$\mathrm{sum}_p=\mathrm{sum}_{2p}+\mathrm{sum}_{2p+1}.$

查询区间可以分成若干个线段树节点管理的区间，答案就是这些区间和的总和。

整段修改只更新总和。 假设当前节点管理 $[L,R]$ ，这段区间完全包含在修改范围中。区间中共有 $R-L+1$ 个位置，每个位置增加 $v$ ，总和就增加

$v(R-L+1).$

因此可以直接执行 $\mathrm{sum}_p\gets\mathrm{sum}_p+v(R-L+1)$ 。若同时递归修改所有叶节点，仍然可能访问整个数组。我们把“这段区间中每个位置还应增加多少”记在当前节点，暂缓更新子节点。

懒标记保存每个位置的增量。 令 $\mathrm{tag}_p$ 表示已经计入 $\mathrm{sum}_p$ 、尚未传给两个子节点的统一增量。完整覆盖当前节点时，执行

$\mathrm{sum}_p\gets\mathrm{sum}_p+v(R-L+1),\qquad \mathrm{tag}_p\gets\mathrm{tag}_p+v.$

多次加法可以合并，例如先增加 $3$ 再增加 $-1$ ，等价于每个位置增加 $2$ 。所以懒标记用加法累计。

这里需要区分两种量： $\mathrm{sum}_p$ 是整段区间的和， $\mathrm{tag}_p$ 是区间内每个位置的待传增量。给总和增加增量时，要乘区间长度；累计懒标记时，直接加上增量。

访问子节点前下传标记。 当修改或查询只涉及当前节点的一部分时，需要访问子节点。此时先把 $\mathrm{tag}_p$ 传给左右子节点：分别给子节点的区间和加上“增量乘以该子区间长度”，再给子节点的懒标记加上同一增量，最后清空 $\mathrm{tag}_p$ 。

例如，节点 $[1,4]$ 整段增加 $3$ 后，它的区间和增加 $12$ ，懒标记为 $3$ 。若之后要查询 $[2,3]$ ，先向子区间 $[1,2]$ 和 $[3,4]$ 分别传递增量 $3$ ，两个子节点的区间和各增加 $6$ ，然后继续向下查询。父节点的区间和已经包含这次增加，下传时保持原值。

对子区间完成修改后，当前节点的标记已清空，重新用左右子节点之和更新父节点即可。查询只汇总答案，下传也只是把已经发生的修改传给子节点，所以查询不会改变数组的实际值。

为什么每次操作只要 $O(\log n)$ 。 递归时，完全被操作区间覆盖的节点直接停止。每一层至多有两个与操作端点相交、还需要继续拆分的节点，其余被访问的节点完整覆盖后就停止。线段树高为 $O(\log n)$ ，因此一次区间修改或查询的时间复杂度都是 $O(\log n)$ 。

部分分说明：

测试点 $1\sim 5$ （ $n,q\le 1000$ ）：直接使用数组模拟区间加法和区间求和，总时间复杂度为 $O(nq)$ 。
测试点 $6\sim 10$ （特殊性质 A，所有修改均满足 $l=r$ ）：用树状数组维护单点增加与前缀和，区间和为两个前缀和之差，每次操作为 $O(\log n)$ 。
测试点 $11\sim 20$ （完整数据）：使用带加法懒标记的线段树，同时支持区间加法与区间求和，每次操作为 $O(\log n)$ 。

实现步骤

开设区间和数组与懒标记数组。数组初始全为 $0$ ，线段树各节点的区间和、标记也都初始化为 $0$ 。
编写整段增加函数：将节点的区间和增加“增量乘以区间长度”，并累计该节点的懒标记。
编写下传函数：把当前节点的增量分别作用于左右子节点，然后清空当前标记。
处理区间修改：若当前区间被完整覆盖，直接整段增加；否则先下传标记，再递归修改有交集的子区间，最后合并左右子节点的区间和。
处理区间查询：若当前区间被完整覆盖，返回区间和；否则先下传标记，再递归查询有交集的子区间，并累加返回值。
依次执行所有操作，每次查询返回相应的区间和。

正确性证明

对线段树维护的状态进行归纳。初始所有元素均为 $0$ ，所有节点的区间和与懒标记也为 $0$ ，状态正确。

对于非叶节点，维护如下关系：它的区间和等于左右子节点保存的区间和之和，再加上当前节点尚未下传的统一增量对整段区间的贡献，即

$\mathrm{sum}_p=\mathrm{sum}_{2p}+\mathrm{sum}_{2p+1} +\mathrm{tag}_p(R-L+1).$

这里子节点可能尚未包含祖先的标记；从根向下递归访问时，先下传路径上的标记，就能使被访问节点包含祖先修改的全部影响。

整段增加时，区间中每个位置增加 $v$ ，区间和增加 $v(R-L+1)$ ，懒标记增加 $v$ ，上述关系保持成立，保存的修改也与题目要求一致。

下传时，将同一增量作用于两个子区间。由于两个子区间不相交且恰好组成父区间，子节点区间和增加的总量为 $\mathrm{tag}_p(R-L+1)$ 。清空父节点标记后，父节点区间和等于两个子节点区间和之和，实际数组的值保持不变。

区间修改部分覆盖当前节点时，先下传，再递归处理所有有交集的子区间。根据归纳假设，子区间中的修改正确，重新合并后父节点区间和也正确。因此每次修改均正确维护数组状态。

区间查询完整覆盖当前节点时，路径上的祖先标记已经下传，直接返回的区间和就是当前实际区间和。部分覆盖时，查询范围被拆成左右两个不相交的部分，递归返回各部分的正确区间和，将它们相加便得到原查询范围的答案。因此算法输出的每个查询结果均正确。

复杂度分析

零初始化需要 $O(n)$ 时间，每次修改或查询需要 $O(\log n)$ 时间，总时间复杂度为 $O(n+q\log n)$ ，空间复杂度为 $O(n)$ 。

参考代码

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

const int N = 200000 + 5;
long long sum[N * 4], tag[N * 4];

// 整段增加 v，先更新区间和，再累计尚未下传的增量。
void upd(int p, int l, int r, long long v) {
    sum[p] += v * (r - l + 1);
    tag[p] += v;
}

void push(int p, int l, int r) {
    if (tag[p] == 0 || l == r) {
        return;
    }
    int m = (l + r) / 2;
    upd(p * 2, l, m, tag[p]);
    upd(p * 2 + 1, m + 1, r, tag[p]);
    tag[p] = 0;  // 增量已经交给两个子节点。
}

void add(int p, int l, int r, int ql, int qr, long long v) {
    if (ql <= l && r <= qr) {
        upd(p, l, r, v);
        return;
    }
    push(p, l, r);
    int m = (l + r) / 2;
    if (ql <= m) {
        add(p * 2, l, m, ql, qr, v);
    }
    if (qr > m) {
        add(p * 2 + 1, m + 1, r, ql, qr, v);
    }
    // 修改子区间后，重新合并父节点的区间和。
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

long long ask(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return sum[p];
    }
    push(p, l, r);
    int m = (l + r) / 2;
    long long ans = 0;  // 累加左右两部分的查询结果。
    if (ql <= m) {
        ans += ask(p * 2, l, m, ql, qr);
    }
    if (qr > m) {
        ans += ask(p * 2 + 1, m + 1, r, ql, qr);
    }
    return ans;
}

int main() {
    freopen("segment.in", "r", stdin);
    freopen("segment.out", "w", stdout);

    int n, q;
    scanf("%d%d", &n, &q);
    // 数组初始全为 0，全局数组也自动清零，直接从根节点操作。
    while (q--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            long long v;
            scanf("%lld", &v);
            add(1, 1, n, l, r, v);
        } else {
            printf("%lld\n", ask(1, 1, n, l, r));
        }
    }
    return 0;
}

D. 树上信标

解题思路

题意分析

设树有 $n$ 个节点。固定一个起点，遍历整棵树就能计算这个起点到所有点的距离，时间复杂度为 $O(n)$ 。如果为每个起点分别做一次遍历，总时间复杂度是 $O(n^2)$ ，只能用于较小的数据。

两个相邻节点作为起点时，到其他点的距离存在简单的变化规律。先求出一个节点的答案，再根据相邻节点的关系逐步求出所有答案，就是本题的换根思路。

先固定根，计算子树信息

暂时把节点 $1$ 作为根。对每个节点 $u$ ，定义两个量：

$\operatorname{sz}[u]=\text{以 }u\text{ 为根的子树中的节点数},$

$\operatorname{f}[u] =\sum_{x\text{ 在 }u\text{ 的子树中}}\operatorname{dist}(u,x).$

子树大小包含节点 $u$ 自身。对于叶子节点，有 $\operatorname{sz}[u]=1$ 、 $\operatorname{f}[u]=0$ 。

设 $v$ 是 $u$ 的一个儿子，边 $(u,v)$ 的长度为 $w$ 。从 $u$ 到 $v$ 子树中的任意节点，都要先经过这条长度为 $w$ 的边，再从 $v$ 走到目标节点。因此，这棵子树对 $\operatorname{f}[u]$ 的贡献是

$\operatorname{f}[v]+\operatorname{sz}[v]\times w.$

遍历 $u$ 的所有儿子，就得到

$\operatorname{sz}[u]=1+\sum_{v\text{ 是 }u\text{ 的儿子}}\operatorname{sz}[v],$

$\operatorname{f}[u] =\sum_{v\text{ 是 }u\text{ 的儿子}} \left(\operatorname{f}[v]+\operatorname{sz}[v]\times w_{u,v}\right).$

由于节点 $1$ 的子树就是整棵树，节点 $1$ 的完整答案为

$\operatorname{ans}[1]=\operatorname{f}[1].$

沿一条边推导换根公式

设 $p$ 是 $u$ 的父节点，边 $(p,u)$ 的长度为 $w$ 。删除这条边，树会分成两部分：一部分是 $u$ 的子树，包含 $\operatorname{sz}[u]$ 个节点；另一部分包含 $n-\operatorname{sz}[u]$ 个节点。

把起点从 $p$ 移到 $u$ 后，对于 $u$ 子树中的节点，起点到它们的路径都减少了边 $(p,u)$ ，每个节点的距离减少 $w$ ，总共减少 $\operatorname{sz}[u]\times w$ 。

对于子树外的节点，起点到它们的路径都新增了边 $(u,p)$ ，每个节点的距离增加 $w$ ，总共增加 $(n-\operatorname{sz}[u])\times w$ 。

两部分合并，得到

$\begin{aligned} \operatorname{ans}[u] &=\operatorname{ans}[p] -\operatorname{sz}[u]\times w +(n-\operatorname{sz}[u])\times w\\ &=\operatorname{ans}[p]+(n-2\operatorname{sz}[u])\times w. \end{aligned}$

这里的 $\operatorname{sz}[u]$ 始终按照最初以节点 $1$ 为根时的父子关系计算。计算不同起点的答案时，只改变距离和，不改变这些子树大小。

用非递归顺序完成两轮计算

可以从节点 $1$ 开始，建立一个遍历序列 $\operatorname{ord}$ 。处理序列中的节点时，把它的儿子追加到末尾，同时记录每个节点的父节点和父边长度。这样，父节点一定出现在儿子之前。

逆序处理 $\operatorname{ord}$ ，每个节点的儿子都已经处理完，可以把当前节点的子树大小和子树距离和累加给父节点。

再顺序处理 $\operatorname{ord}$ ，每个节点的父节点答案都已经求出，可以使用换根公式计算当前节点的答案。两轮计算都只处理每条父子关系一次。

当树是一条长度很大的链时，递归深度可能达到 $n$ 。参考代码使用遍历序列完成上述过程，额外调用栈深度为常数。

数值范围与输出

距离和需要使用足够大的整数类型。考虑 $n=200000$ 、每条边长为 $10^9$ 的一条链。从端点出发，到各点的距离依次为 $0,10^9,2\times10^9,\ldots,(n-1)\times10^9$ ，距离总和为

$10^9\sum_{i=0}^{n-1}i =10^9\times\frac{200000\times199999}{2} =19999900000000000000.$

这个值超过有符号 long long 的最大值 $9223372036854775807$ 。因此，参考代码使用 __int128 保存 $\operatorname{f}$ 、 $\operatorname{ans}$ ，并在乘法之前转换到 __int128。边权本身使用 long long 保存即可。

printf 没有直接输出 __int128 的格式符，可以不断取十进制末位，把得到的数字逆序后输出。所有答案均为非负整数；当 $n=1$ 时，唯一节点的答案是 $0$ ，输出函数也要能处理这一情况。

部分分说明：

测试点 $1\sim5$ （ $n\le1000$ ）：枚举每个起点，分别遍历整棵树，累加从该起点出发的所有距离，总时间复杂度为 $O(n^2)$ 。
测试点 $6\sim10$ （特殊性质 A，整棵树是一条链）：从端点出发恢复链上节点的顺序，设第 $i$ 个节点的位置为 $x_i$ ，前缀和为 $P_i=\sum_{j=1}^{i}x_j$ ，且 $P_0=0$ 。它到左侧节点的距离和为 $(i-1)x_i-P_{i-1}$ ，到右侧节点的距离和为 $(P_n-P_i)-(n-i)x_i$ ，两部分相加即可。恢复顺序、计算前缀和以及求全部答案的时间复杂度均为 $O(n)$ ，位置前缀和及答案使用 __int128。也可以先求一个端点的答案，再按相邻节点间的距离变化逐点递推。 $n=1$ 时直接输出 $0$ 。
测试点 $11\sim20$ （无额外限制）：使用完整的换根算法，逆序计算子树大小和子树距离和，再顺序求出所有节点的答案，总时间复杂度为 $O(n)$ 。

实现步骤

读入树，使用邻接表保存每条无向边的两个方向。
从节点 $1$ 开始生成遍历序列 $\operatorname{ord}$ ，记录每个节点的父节点 $\operatorname{fa}[u]$ 和父边长度 $\operatorname{pw}[u]$ 。
初始化所有 $\operatorname{sz}[u]=1$ 、 $\operatorname{f}[u]=0$ 。
逆序处理序列中除根以外的节点 $u$ ，令 $p=\operatorname{fa}[u]$ ，将 $\operatorname{sz}[u]$ 累加到 $\operatorname{sz}[p]$ ，将 $\operatorname{f}[u]+\operatorname{sz}[u]\times\operatorname{pw}[u]$ 累加到 $\operatorname{f}[p]$ 。
设置 $\operatorname{ans}[1]=\operatorname{f}[1]$ 。
顺序处理序列中除根以外的节点 $u$ ，计算 $\operatorname{ans}[u]=\operatorname{ans}[\operatorname{fa}[u]]+(n-2\operatorname{sz}[u])\times\operatorname{pw}[u]$ 。
按节点编号从小到大，把每个 __int128 答案转成十进制输出。

正确性证明

首先证明逆序计算得到的子树信息正确。

叶子节点的子树只有它自身，所以初始化的 $\operatorname{sz}[u]=1$ 、 $\operatorname{f}[u]=0$ 正确。对于任意非叶子节点 $u$ ，逆序处理保证它的全部儿子已经处理完成。不同儿子的子树互不相交，与节点 $u$ 自身恰好组成 $u$ 的子树，因此大小累加得到正确的 $\operatorname{sz}[u]$ 。对每个儿子 $v$ ，到它子树内所有节点的距离贡献为 $\operatorname{f}[v]+\operatorname{sz}[v]\times w_{u,v}$ ，累加后得到正确的 $\operatorname{f}[u]$ 。由此，全部子树信息正确， $\operatorname{ans}[1]=\operatorname{f}[1]$ 也正确。

其次证明换根计算正确。设 $\operatorname{ans}[p]$ 已经正确， $u$ 是 $p$ 的儿子。删去边 $(p,u)$ 后，所有节点被完整地分成 $u$ 的子树和子树外两部分。起点由 $p$ 移到 $u$ 时，这两部分的距离总和分别减少 $\operatorname{sz}[u]\times w$ 、增加 $(n-\operatorname{sz}[u])\times w$ 。因此，换根公式准确计算出 $\operatorname{ans}[u]$ 。

顺序遍历中，父节点总在儿子之前。以正确的 $\operatorname{ans}[1]$ 为起点归纳，全部节点的答案都正确。最终按照节点编号输出，因此算法符合题目要求。

复杂度分析

建立遍历序列时，每条无向边被检查两次；逆序计算和顺序换根各处理 $n-1$ 条父子关系。因此，总时间复杂度为 $O(n)$ 。

邻接表、遍历序列以及各状态数组占用 $O(n)$ 空间。十进制输出的位数有固定上界，不改变上述复杂度。

参考代码

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

using ll = long long;
using i128 = __int128;

struct Edge {
    int to;
    ll w;
};

// 逐位拆出十进制数字，再倒序输出。
void out(i128 x) {
    char s[50];
    int k = 0;
    do {
        s[k++] = char('0' + x % 10);
        x /= 10;
    } while (x > 0);
    reverse(s, s + k);
    s[k] = '\0';
    printf("%s", s);
}

int main() {
    freopen("reroot.in", "r", stdin);
    freopen("reroot.out", "w", stdout);

    int n;
    if (scanf("%d", &n) != 1) {
        return 0;
    }

    vector<vector<Edge>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        ll w;
        scanf("%d%d%lld", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> fa(n + 1), sz(n + 1, 1), ord;
    vector<ll> pw(n + 1);
    vector<i128> f(n + 1), ans(n + 1);
    ord.reserve(n);
    ord.push_back(1);

    // 用数组顺序遍历，保证父节点排在子节点之前。
    for (int i = 0; i < (int)ord.size(); ++i) {
        int u = ord[i];
        for (Edge e : g[u]) {
            int v = e.to;
            if (v == fa[u]) {
                continue;
            }
            fa[v] = u;
            pw[v] = e.w;
            ord.push_back(v);
        }
    }

    // 逆序将每棵子树的大小、距离和累加给父节点。
    for (int i = n - 1; i >= 1; --i) {
        int u = ord[i];
        int p = fa[u];
        sz[p] += sz[u];
        f[p] += f[u] + (i128)sz[u] * pw[u];
    }

    ans[1] = f[1];  // 根节点的子树包含整棵树。

    // 顺序换根，每次根据父节点答案计算子节点答案。
    for (int i = 1; i < n; ++i) {
        int u = ord[i];
        int p = fa[u];
        ans[u] = ans[p] + (i128)(n - 2 * sz[u]) * pw[u];
    }

    for (int u = 1; u <= n; ++u) {
        out(ans[u]);
        printf("%c", u == n ? '\n' : ' ');
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 19

/yiw
呃🤔为什么要放线段树板子

3天前来自山东
13
- GO_DOWN_Replace
  回复
  /yiw
  https://chat.deepseek.com/share/bqumr182q7v1gz03z8
  
  因为这是 DeepSeek 出的题
  
  10小时前来自四川
  3
柠檬
666

2天前来自广东
12
Deep欠揍 | 深度欠揍
比赛都还没结束就发这种东西吗

4天前来自浙江
10
- GO_DOWN_Replace
  回复
  Deep欠揍 | 深度欠揍
  https://chat.deepseek.com/a/chat/s/dbc32786-b7ef-4d80-8336-0f60c4576ef7
  
  10小时前来自四川
  0
干拉小子
1

2天前来自浙江
9
༺ཌༀ神༒曦༃ༀད༻
kan'bu'don

4天前来自新疆
7
- 小u伤
  回复
  ༺ཌༀ神༒曦༃ༀད༻
  Hh
  
  2天前来自浙江
  1
༺དༀ༒༺wzw不cai༒ༀཌ༻
所以作者S组满分了？

1小时前来自江苏
1
Xylophone
黄绿绿绿

昨天来自广东
1
- Xylophone
  回复
  Xylophone
  T4 好像是黄来着
  
  昨天来自广东
  1
- Zzzzzzsr（单身十年换S1
  回复
  Xylophone
  T2黄，T3红，T4黄
  
  昨天来自广东
  1
- Xylophone
  回复
  Zzzzzzsr（单身十年换S1
  潘德里
  
  昨天来自广东
  1
天之神_三角洲行动_威龙－O－
2天前来自浙江
1
天之神_三角洲行动_威龙－O－
~~rcfunherugvnurghneufdixo2dciufvc3748r789345y~~

2天前来自浙江
1
天之神_三角洲行动_威龙－O－
gtviegv

2天前来自浙江
1
天之神_三角洲行动_威龙－O－
==riotgjrbhjevioh ==

2天前来自浙江
1
天之神_三角洲行动_威龙－O－
~~rotfgnmhjtiogjpnhiotjbuiotrhgvuntrheguocnhms~~

2天前来自浙江
1
天之神_三角洲行动_威龙－O－
ii

2天前来自浙江
1
Zzzzzzsr（单身十年换S1
老师，请求审核并置顶非官方题解 https://www.acgo.cn/discuss/study/97347，辛苦老师

4天前来自广东
1
- 小u伤
  回复
  Zzzzzzsr（单身十年换S1
  y
  
  2天前来自浙江
  0
- 小u伤
  回复
  Zzzzzzsr（单身十年换S1
  Fg
  
  2天前来自浙江
  0
- 小u伤
  回复
  小u伤
  H
  
  2天前来自浙江
  0
༺ཌༀཉི༒无敌草履虫༒༃ༀད༻
比赛都还没结束就发这种东西吗

22分钟前来自浙江
0
DaowohaoDeshigay
1

9小时前来自浙江
0
白鸽乌鸦相爱的戏码
666

10小时前来自上海
0
GO_DOWN_Replace
https://chat.deepseek.com/share/bqumr182q7v1gz03z8

你怎么解释

10小时前来自四川
0
- GO_DOWN_Replace
  回复
  GO_DOWN_Replace
  这是我刚刚用 DeepSeek 直接生成的
  
  10小时前来自四川
  0
CXY
666

昨天来自贵州
0