目录

题号	题目	完整算法	时间复杂度	空间复杂度
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)$。这一做法也适用于前面的全部测试点。

实现步骤

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

实现步骤

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

实现步骤

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

正确性证明

对线段树维护的状态进行归纳。初始所有元素均为 $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. 读入树，使用邻接表保存每条无向边的两个方向。
2. 从节点 $1$ 开始生成遍历序列 $\operatorname{ord}$，记录每个节点的父节点 $\operatorname{fa}[u]$ 和父边长度 $\operatorname{pw}[u]$。
3. 初始化所有 $\operatorname{sz}[u]=1$、$\operatorname{f}[u]=0$。
4. 逆序处理序列中除根以外的节点 $u$，令 $p=\operatorname{fa}[u]$，将 $\operatorname{sz}[u]$ 累加到 $\operatorname{sz}[p]$，将 $\operatorname{f}[u]+\operatorname{sz}[u]\times\operatorname{pw}[u]$ 累加到 $\operatorname{f}[p]$。
5. 设置 $\operatorname{ans}[1]=\operatorname{f}[1]$。
6. 顺序处理序列中除根以外的节点 $u$，计算 $\operatorname{ans}[u]=\operatorname{ans}[\operatorname{fa}[u]]+(n-2\operatorname{sz}[u])\times\operatorname{pw}[u]$。
7. 按节点编号从小到大，把每个 __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;
}