10
目录
题号 题目 完整算法 时间复杂度 空间复杂度 A 灯塔巡航 排序、二分、动态规划 O(nlogn)O(n\log n)O(nlogn) O(n)O(n)O(n) B 优惠通道 分层状态图、Dijkstra O((n+m)log(n+m))O((n+m)\log(n+m))O((n+m)log(n+m)) O(n+m)O(n+m)O(n+m) C 区间能量 懒标记线段树 O(n+qlogn)O(n+q\log n)O(n+qlogn) O(n)O(n)O(n) D 树上信标 换根动态规划 O(n)O(n)O(n) O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A. 灯塔巡航
解题思路
题意分析
记任务数量为 nnn,第 iii 个任务的时间区间为 [li,ri)[l_i,r_i)[li ,ri )、能量为 viv_ivi 。首先考虑按时间顺序执行任务。若一个方案中的任务互不冲突,它们就能按结束时刻从小到大排列。于是先将所有任务按照结束时刻排序,之后只需研究排序后的任务前缀。下文的任务编号均指排序后的编号。
任务能量不同时,只看某个局部条件无法决定是否选择任务。单个任务能量较高,也可能挤占其他任务的执行时间,导致总能量更低。因此,需要同时比较“选择当前任务”和“跳过当前任务”两类方案。
定义 dp[i]\mathrm{dp}[i]dp[i] 为只考虑前 iii 个任务时,能够获得的最大能量。这里“考虑”表示这些任务允许被选择,并不要求全部执行。没有任务时,dp[0]=0\mathrm{dp}[0]=0dp[0]=0。
对第 iii 个任务分类讨论。如果跳过它,其他任务都在前 i−1i-1i−1 个任务中,最优收益就是 dp[i−1]\mathrm{dp}[i-1]dp[i−1]。
如果选择它,之前执行的任务必须在时刻 lil_ili 或更早结束,即满足 rj≤lir_j\le l_irj ≤li 。由于结束时刻已经有序,这些任务恰好组成一个前缀。令 pip_ipi 为前 i−1i-1i−1 个任务中满足 rj≤lir_j\le l_irj ≤li 的任务数量,那么可以从前 pip_ipi 个任务中选出最优方案,再接上当前任务,获得 dp[pi]+vi\mathrm{dp}[p_i]+v_idp[pi ]+vi 点能量。若没有任务能衔接,便有 pi=0p_i=0pi =0。
因此状态转移为
dp[i]=max(dp[i−1], dp[pi]+vi).\mathrm{dp}[i]=\max\bigl(\mathrm{dp}[i-1],\ \mathrm{dp}[p_i]+v_i\bigr). dp[i]=max(dp[i−1], dp[pi ]+vi ).
这里可以将前 pip_ipi 个任务的任意合法方案直接接到任务 iii 之前:该前缀内每个任务的结束时刻都不大于 lil_ili ,所以整个方案必然已在当前任务开始前完成。
现在只剩下如何快速求出 pip_ipi 。若逐个向前扫描,每个任务最多检查 nnn 个前驱,总计需要 O(n2)O(n^2)O(n2) 时间。结束时刻有序,可以使用二分查找,将一次查询缩短到 O(logn)O(\log n)O(logn)。
具体来说,upper_bound 找到第一个严格大于 lil_ili 的结束时刻,它前面的元素数量就是 pip_ipi 。必须保留结束时刻恰好等于 lil_ili 的任务,才能符合半开区间的衔接规则。参考代码中的任务数组从下标 000 开始,而动态规划数组从下标 111 开始;二分查找得到的是可用前缀的长度,可以直接作为动态规划下标。
最终,dp[n]\mathrm{dp}[n]dp[n] 就是所有任务的最优答案。
部分分说明:
* 测试点 1∼51\sim51∼5(n≤1000n\le1000n≤1000,ri≤104r_i\le10^4ri ≤104,vi≤103v_i\le10^3vi ≤103):按结束时刻排序,使用同样的动态规划,但通过逐个扫描前面的任务求出 pip_ipi 。时间复杂度为 O(n2)O(n^2)O(n2),可以处理这一组数据。
* 测试点 6∼106\sim106∼10(所有任务满足 vi=Vv_i=Vvi =V):总能量等于选择的任务数乘以 VVV,转为最大化互不冲突的任务数量。按结束时刻排序,每次选择最早结束且能够衔接的任务。最早结束的选择会给后续任务留下尽可能多的时间,因此区间选择贪心可以处理这一组数据。
* 测试点 11∼1511\sim1511∼15(ri≤106r_i\le10^6ri ≤106):可以按整数时刻做动态规划。令 f[t]f[t]f[t] 表示所有选中任务不晚于时刻 ttt 完成时能获得的最大能量,将任务按结束时刻分组,计算 f[t]=max(f[t−1], maxri=t(f[li]+vi))f[t]=\max\bigl(f[t-1],\ \max_{r_i=t}(f[l_i]+v_i)\bigr)f[t]=max(f[t−1], maxri =t (f[li ]+vi )),初始化 f[0]=0f[0]=0f[0]=0。由于 li<ril_i<r_ili <ri
,转移时需要的状态均已算出。令 T=maxriT=\max r_iT=maxri ,时间与空间复杂度均可控制在 O(n+T)O(n+T)O(n+T)。
* 测试点 16∼2016\sim2016∼20(完整数据范围):结束时刻可达 10910^9109,使用按结束时刻排序、二分查找前驱的动态规划,时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。这一做法也适用于前面的全部测试点。
实现步骤
1. 读入所有任务,按照结束时刻从小到大排序,并保存排序后的结束时刻数组。
2. 建立长度为 n+1n+1n+1 的动态规划数组,将 dp[0]\mathrm{dp}[0]dp[0] 初始化为 000。
3. 按顺序处理第 iii 个任务,在前 i−1i-1i−1 个结束时刻中使用 upper_bound 求出 pip_ipi 。
4. 按照转移式比较跳过和选择当前任务的收益,得到 dp[i]\mathrm{dp}[i]dp[i]。
5. 输出 dp[n]\mathrm{dp}[n]dp[n]。
正确性证明
对考虑的任务数量 iii 进行归纳,证明 dp[i]\mathrm{dp}[i]dp[i] 等于前 iii 个任务的最优收益。
当 i=0i=0i=0 时,没有任务可以执行,最大收益为 000,与初始化一致。
假设所有下标小于 iii 的状态都已正确求出。考察前 iii 个任务的任意最优方案。
若方案没有选择第 iii 个任务,它完全由前 i−1i-1i−1 个任务组成,收益至多为 dp[i−1]\mathrm{dp}[i-1]dp[i−1];由归纳假设,该收益也确实能够达到。
若方案选择了第 iii 个任务,因为第 iii 个任务的结束时刻在前 iii 个任务中最晚,且每个任务都有 lj<rjl_j<r_jlj <rj ,其他任务不可能安排在它之后,只能在它开始前结束。这些任务均满足 rj≤lir_j\le l_irj ≤li ,属于前 pip_ipi 个任务,所以它们的总收益至多为 dp[pi]\mathrm{dp}[p_i]dp[pi ]。反过来,前 pip_ipi 个任务的最优方案能够合法地接上第 iii 个任务,达到 dp[pi]+vi\mathrm{dp}[p_i]+v_idp[pi ]+vi 。
两类方案覆盖了所有可能,分别取各类最大收益再取最大值,就得到正确的 dp[i]\mathrm{dp}[i]dp[i]。由数学归纳法,最终输出的 dp[n]\mathrm{dp}[n]dp[n] 正确。
复杂度分析
排序需要 O(nlogn)O(n\log n)O(nlogn) 时间,每个任务进行一次 O(logn)O(\log n)O(logn) 的二分查找与一次常数时间的转移,总时间复杂度为 O(nlogn)O(n\log n)O(nlogn)。任务数组、结束时刻数组和动态规划数组共占用 O(n)O(n)O(n) 空间。
参考代码
B. 优惠通道
解题思路
题意分析
设原图有 nnn 个路口和 mmm 条双向道路,起点为 111,终点为 nnn。普通最短路只记录到达每个路口的最小时间。但在本题中,到达同一个路口的两条路线,还可能具有不同的优惠券使用情况。
例如,到达某个路口时,一条路线耗时较少,但优惠券已经使用;另一条路线耗时略多,却保留着优惠券。若后面有一条耗时很大的道路,第二种状态就可能得到更好的最终结果。因此,不能只保留一个最短距离,需要将“优惠券是否已经使用”也加入状态。
将状态记为 (u,k)(u,k)(u,k),其中 uuu 是当前路口,k=0k=0k=0 表示优惠券尚未使用,k=1k=1k=1 表示已经使用。定义 d[u][k]\mathrm{d}[u][k]d[u][k] 为从起点出发,到达这一状态的最小耗时。初始时人在路口 111,优惠券尚未使用,所以
d[1][0]=0,\mathrm{d}[1][0]=0, d[1][0]=0,
其余状态暂设为无穷大。
现在考虑从路口 uuu 沿一条权值为 www 的道路走到路口 vvv。如果正常通行,优惠券的使用情况保持不变,状态转移为
(u,k)⟶(v,k),费用为 w.(u,k)\longrightarrow(v,k),\qquad \text{费用为 }w. (u,k)⟶(v,k),费用为 w.
如果优惠券还未使用,还可以在这次经过道路时使用它,使当前费用变为 000,状态转移为
(u,0)⟶(v,1),费用为 0.(u,0)\longrightarrow(v,1),\qquad \text{费用为 }0. (u,0)⟶(v,1),费用为 0.
已经使用优惠券的状态只允许继续正常通行。这样,任意一条状态转移路径最多只会发生一次从未使用到已使用的变化,也就准确地限制了优惠券的使用次数。
可以将每个原图路口拆成两个状态。这个状态图共有 2n2n2n 个点;原图每条无向道路对应两种方向,每个方向有两条正常通行的状态边,以及一条使用优惠券的状态边,因此状态边数为 6m6m6m。实际编程时保存原图邻接表,在遍历道路时进行上述转移即可。
所有状态边的权值都非负,包括使用优惠券产生的零权边,因此可以使用 Dijkstra 算法。用小根堆维护当前距离最小的待处理状态,每次取出后沿原图相邻道路进行松弛。一个状态的距离被改小时,将新的记录放入堆中;之后若取出的记录已经过期,就直接跳过。
到达终点时,优惠券可以已经使用,也可以仍然保留,所以答案为
min(d[n][0], d[n][1]).\min\bigl(\mathrm{d}[n][0],\ \mathrm{d}[n][1]\bigr). min(d[n][0], d[n][1]).
若两者都是无穷大,终点不可达,输出 -1。特别地,当 n=1n=1n=1 时,已经位于终点,可以不经过道路、不使用优惠券,正确答案为 000;对两个状态取最小值会自然地覆盖这种情况。
部分分说明:
* 测试点 1∼51\sim51∼5(n,m≤1000n,m\le1000n,m≤1000):仍然使用两个优惠券状态,但采用朴素 Dijkstra。每轮扫描全部 2n2n2n 个状态,选出尚未确定且距离最小的状态,再通过邻接表进行松弛。时间复杂度为 O(n2+m)O(n^2+m)O(n2+m),可以处理这一组数据。
* 测试点 6∼106\sim106∼10(n,m≤2×105n,m\le2\times10^5n,m≤2×105,每条道路的权值均为 WWW):一条经过 kkk 条道路的路线,最小耗时是 max(k−1,0)W\max(k-1,0)Wmax(k−1,0)W。这一值随 kkk 增大而不减,因此对原图运行 BFS,求出从 111 到 nnn 最少需要经过多少条道路即可。若不可达输出 -1,否则用该公式计算答案,时间复杂度为 O(n+m)O(n+m)O(n+m)。
* 测试点 11∼2011\sim2011∼20(完整数据范围):使用状态扩展和堆优化 Dijkstra。该做法适用于所有测试点。
实现步骤
1. 读入道路,按照双向道路建立邻接表。
2. 将所有距离初始化为无穷大,令 d[1][0]=0\mathrm{d}[1][0]=0d[1][0]=0,把状态 (1,0)(1,0)(1,0) 及距离 000 放入小根堆。
3. 取出距离最小的状态;如果堆中的距离与当前记录不一致,跳过这条过期记录。
4. 遍历相邻道路,尝试正常通行,更新相同优惠券状态下的距离。
5. 如果当前优惠券尚未使用,再尝试免费经过该道路,更新已使用优惠券的状态。每次成功更新后,将新记录放入堆。
6. 堆为空后,取终点两个状态距离的最小值;不可达时输出 -1,否则输出这一最小值。
正确性证明
首先证明原问题中的合法路线与状态图中的路径相互对应,并且总费用相同。
给定一条至多使用一次优惠券的合法路线,从状态 (1,0)(1,0)(1,0) 开始。正常经过道路时,走状态图中费用为原边权且优惠券状态不变的边;若在某次经过道路时使用优惠券,就走从未使用状态到已使用状态的零权边。这样能够到达终点的某个状态,且每次经过道路的计费方式与原路线一致。
反过来,给定一条从 (1,0)(1,0)(1,0) 出发的状态图路径,将每次转移还原为原图中的道路经过。状态图只允许从未使用状态转为已使用状态,不能反向恢复,因此路径至多包含一次免费经过。还原后得到合法路线,且费用保持不变。
于是,题目要求的最小耗时等于状态图中从 (1,0)(1,0)(1,0) 到 (n,0)(n,0)(n,0)、(n,1)(n,1)(n,1) 的最短距离的较小值。
状态图所有边的权值均非负。Dijkstra 每次选择当前距离最小的未确定状态时,如果存在更短路径,则该路径上第一个未确定状态的前驱已经被处理过,相应松弛会给出不大于这条更短路径前缀的距离。由于之后的边权非负,这会与当前选出的距离最小性矛盾。因此每次确定的距离正确,所有可达状态的最短距离都能正确求出。
最终取终点两个状态的较小距离,恰好涵盖使用和不使用优惠券的全部合法路线;两者均不可达时输出 -1。因此算法正确。
复杂度分析
状态图有 2n2n2n 个状态和 6m6m6m 条有向状态边。邻接表建图需要 O(n+m)O(n+m)O(n+m) 时间,堆优化 Dijkstra 的时间复杂度为 O((n+m)log(n+m))O((n+m)\log(n+m))O((n+m)log(n+m)),距离、邻接表和堆共占用 O(n+m)O(n+m)O(n+m) 空间。这里用 log(n+m)\log(n+m)log(n+m) 计入堆中可能保留的过期记录。
参考代码
C. 区间能量
解题思路
题意分析
设数组长度为 nnn,操作次数为 qqq,数组初始全为 000。
从直接维护数组开始。 对区间 [l,r][l,r][l,r] 加上 vvv 时,逐个修改数组中的元素;查询时,逐个累加区间中的元素。每次操作最多访问 nnn 个位置,总时间复杂度为 O(nq)O(nq)O(nq)。当 n,q≤1000n,q\le 1000n,q≤1000 时,这个方法可以完成计算;当两者都达到 2×1052\times 10^52×105 时,需要更快的区间维护方法。
静态数组可以用前缀和快速查询,但本题修改与查询交替出现。一次区间修改会影响多个前缀和,逐个重新维护仍可能花费 O(n)O(n)O(n) 时间。我们需要同时加速区间修改和区间查询。
用线段树维护区间和。 线段树根节点管理 [1,n][1,n][1,n],每个非叶节点将所管理的区间 [L,R][L,R][L,R] 分成 [L,M][L,M][L,M] 与 [M+1,R][M+1,R][M+1,R],其中 M=⌊(L+R)/2⌋M=\lfloor(L+R)/2\rfloorM=⌊(L+R)/2⌋。节点 ppp 用 sump\mathrm{sum}_psump 保存其区间的元素和。若左右子节点都已包含应有的修改,父节点的和等于左右子节点的和:
sump=sum2p+sum2p+1.\mathrm{sum}_p=\mathrm{sum}_{2p}+\mathrm{sum}_{2p+1}. sump =sum2p +sum2p+1 .
查询区间可以分成若干个线段树节点管理的区间,答案就是这些区间和的总和。
整段修改只更新总和。 假设当前节点管理 [L,R][L,R][L,R],这段区间完全包含在修改范围中。区间中共有 R−L+1R-L+1R−L+1 个位置,每个位置增加 vvv,总和就增加
v(R−L+1).v(R-L+1). v(R−L+1).
因此可以直接执行 sump←sump+v(R−L+1)\mathrm{sum}_p\gets\mathrm{sum}_p+v(R-L****ump ←sump +v(R−L+1)。若同时递归修改所有叶节点,仍然可能访问整个数组。我们把“这段区间中每个位置还应增加多少”记在当前节点,暂缓更新子节点。
懒标记保存每个位置的增量。 令 tagp\mathrm{tag}_ptagp 表示已经计入 sump\mathrm{sum}_psump 、尚未传给两个子节点的统一增量。完整覆盖当前节点时,执行
sump←sump+v(R−L+1),tagp←tagp+v.\mathrm{sum}_p\gets\mathrm{sum}_p+v(R-L+1),\qquad \mathrm{tag}_p\gets\mathrm{tag}_p+v. sump ←sump +v(R−L+1),tagp ←tagp +v.
多次加法可以合并,例如先增加 333 再增加 −1-1−1,等价于每个位置增加 222。所以懒标记用加法累计。
这里需要区分两种量:sump\mathrm{sum}_psump 是整段区间的和,tagp\mathrm{tag}_ptagp 是区间内每个位置的待传增量。给总和增加增量时,要乘区间长度;累计懒标记时,直接加上增量。
访问子节点前下传标记。 当修改或查询只涉及当前节点的一部分时,需要访问子节点。此时先把 tagp\mathrm{tag}_ptagp 传给左右子节点:分别给子节点的区间和加上“增量乘以该子区间长度”,再给子节点的懒标记加上同一增量,最后清空 tagp\mathrm{tag}_ptagp 。
例如,节点 [1,4][1,4][1,4] 整段增加 333 后,它的区间和增加 121212,懒标记为 333。若之后要查询 [2,3][2,3][2,3],先向子区间 [1,2][1,2][1,2] 和 [3,4][3,4][3,4] 分别传递增量 333,两个子节点的区间和各增加 666,然后继续向下查询。父节点的区间和已经包含这次增加,下传时保持原值。
对子区间完成修改后,当前节点的标记已清空,重新用左右子节点之和更新父节点即可。查询只汇总答案,下传也只是把已经发生的修改传给子节点,所以查询不会改变数组的实际值。
为什么每次操作只要 O(logn)O(\log n)O(logn)。 递归时,完全被操作区间覆盖的节点直接停止。每一层至多有两个与操作端点相交、还需要继续拆分的节点,其余被访问的节点完整覆盖后就停止。线段树高为 O(logn)O(\log n)O(logn),因此一次区间修改或查询的时间复杂度都是 O(logn)O(\log n)O(logn)。
部分分说明:
* 测试点 1∼51\sim 51∼5(n,q≤1000n,q\le 1000n,q≤1000):直接使用数组模拟区间加法和区间求和,总时间复杂度为 O(nq)O(nq)O(nq)。
* 测试点 6∼106\sim 106∼10(特殊性质 A,所有修改均满足 l=rl=rl=r):用树状数组维护单点增加与前缀和,区间和为两个前缀和之差,每次操作为 O(logn)O(\log n)O(logn)。
* 测试点 11∼2011\sim 2011∼20(完整数据):使用带加法懒标记的线段树,同时支持区间加法与区间求和,每次操作为 O(logn)O(\log n)O(logn)。
实现步骤
1. 开设区间和数组与懒标记数组。数组初始全为 000,线段树各节点的区间和、标记也都初始化为 000。
2. 编写整段增加函数:将节点的区间和增加“增量乘以区间长度”,并累计该节点的懒标记。
3. 编写下传函数:把当前节点的增量分别作用于左右子节点,然后清空当前标记。
4. 处理区间修改:若当前区间被完整覆盖,直接整段增加;否则先下传标记,再递归修改有交集的子区间,最后合并左右子节点的区间和。
5. 处理区间查询:若当前区间被完整覆盖,返回区间和;否则先下传标记,再递归查询有交集的子区间,并累加返回值。
6. 依次执行所有操作,每次查询返回相应的区间和。
正确性证明
对线段树维护的状态进行归纳。初始所有元素均为 000,所有节点的区间和与懒标记也为 000,状态正确。
对于非叶节点,维护如下关系:它的区间和等于左右子节点保存的区间和之和,再加上当前节点尚未下传的统一增量对整段区间的贡献,即
sump=sum2p+sum2p+1+tagp(R−L+1).\mathrm{sum}_p=\mathrm{sum}_{2p}+\mathrm{sum}_{2p+1} +\mathrm{tag}_p(R-L+1). sump =sum2p +sum2p+1 +tagp (R−L+1).
这里子节点可能尚未包含祖先的标记;从根向下递归访问时,先下传路径上的标记,就能使被访问节点包含祖先修改的全部影响。
整段增加时,区间中每个位置增加 vvv,区间和增加 v(R−L+1)v(R-L+1)v(R−L+1),懒标记增加 vvv,上述关系保持成立,保存的修改也与题目要求一致。
下传时,将同一增量作用于两个子区间。由于两个子区间不相交且恰好组成父区间,子节点区间和增加的总量为 tagp(R−L+1)\mathrm{tag}_p(R-L+1)tagp (R−L+1)。清空父节点标记后,父节点区间和等于两个子节点区间和之和,实际数组的值保持不变。
区间修改部分覆盖当前节点时,先下传,再递归处理所有有交集的子区间。根据归纳假设,子区间中的修改正确,重新合并后父节点区间和也正确。因此每次修改均正确维护数组状态。
区间查询完整覆盖当前节点时,路径上的祖先标记已经下传,直接返回的区间和就是当前实际区间和。部分覆盖时,查询范围被拆成左右两个不相交的部分,递归返回各部分的正确区间和,将它们相加便得到原查询范围的答案。因此算法输出的每个查询结果均正确。
复杂度分析
零初始化需要 O(n)O(n)O(n) 时间,每次修改或查询需要 O(logn)O(\log n)O(logn) 时间,总时间复杂度为 O(n+qlogn)O(n+q\log n)O(n+qlogn),空间复杂度为 O(n)O(n)O(n)。
参考代码
D. 树上信标
解题思路
题意分析
设树有 nnn 个节点。固定一个起点,遍历整棵树就能计算这个起点到所有点的距离,时间复杂度为 O(n)O(n)O(n)。如果为每个起点分别做一次遍历,总时间复杂度是 O(n2)O(n^2)O(n2),只能用于较小的数据。
两个相邻节点作为起点时,到其他点的距离存在简单的变化规律。先求出一个节点的答案,再根据相邻节点的关系逐步求出所有答案,就是本题的换根思路。
先固定根,计算子树信息
暂时把节点 111 作为根。对每个节点 uuu,定义两个量:
sz[u]=以 u 为根的子树中的节点数,\operatorname{sz}[u]=\text{以 }u\text{ 为根的子树中的节点数}, sz[u]=以 u 为根的子树中的节点数,
f[u]=∑x 在 u 的子树中dist(u,x).\operatorname{f}[u] =\sum_{x\text{ 在 }u\text{ 的子树中}}\operatorname{dist}(u,x). f[u]=x 在 u 的子树中∑ dist(u,x).
子树大小包含节点 uuu 自身。对于叶子节点,有 sz[u]=1\operatorname{sz}[u]=1sz[u]=1、f[u]=0\operatorname{f}[u]=0f[u]=0。
设 vvv 是 uuu 的一个儿子,边 (u,v)(u,v)(u,v) 的长度为 www。从 uuu 到 vvv 子树中的任意节点,都要先经过这条长度为 www 的边,再从 vvv 走到目标节点。因此,这棵子树对 f[u]\operatorname{f}[u]f[u] 的贡献是
f[v]+sz[v]×w.\operatorname{f}[v]+\operatorname{sz}[v]\times w. f[v]+sz[v]×w.
遍历 uuu 的所有儿子,就得到
sz[u]=1+∑v 是 u 的儿子sz[v],\operatorname{sz}[u]=1+\sum_{v\text{ 是 }u\text{ 的儿子}}\operatorname{sz}[v], sz[u]=1+v 是 u 的儿子∑ sz[v],
f[u]=∑v 是 u 的儿子(f[v]+sz[v]×wu,v).\operatorname{f}[u] =\sum_{v\text{ 是 }u\text{ 的儿子}} \left(\operatorname{f}[v]+\operatorname{sz}[v]\times w_{u,v}\right). f[u]=v 是 u 的儿子∑ (f[v]+sz[v]×wu,v ).
由于节点 111 的子树就是整棵树,节点 111 的完整答案为
ans[1]=f[1].\operatorname{ans}[1]=\operatorname{f}[1]. ans[1]=f[1].
沿一条边推导换根公式
设 ppp 是 uuu 的父节点,边 (p,u)(p,u)(p,u) 的长度为 www。删除这条边,树会分成两部分:一部分是 uuu 的子树,包含 sz[u]\operatorname{sz}[u]sz[u] 个节点;另一部分包含 n−sz[u]n-\operatorname{sz}[u]n−sz[u] 个节点。
把起点从 ppp 移到 uuu 后,对于 uuu 子树中的节点,起点到它们的路径都减少了边 (p,u)(p,u)(p,u),每个节点的距离减少 www,总共减少 sz[u]×w\operatorname{sz}[u]\times wsz[u]×w。
对于子树外的节点,起点到它们的路径都新增了边 (u,p)(u,p)(u,p),每个节点的距离增加 www,总共增加 (n−sz[u])×w(n-\operatorname{sz}[u])\times w(n−sz[u])×w。
两部分合并,得到
ans[u]=ans[p]−sz[u]×w+(n−sz[u])×w=ans[p]+(n−2sz[u])×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} ans[u]
=ans[p]−sz[u]×w+(n−sz[u])×w=ans[p]+(n−2sz[u])×w.
这里的 sz[u]\operatorname{sz}[u]sz[u] 始终按照最初以节点 111 为根时的父子关系计算。计算不同起点的答案时,只改变距离和,不改变这些子树大小。
用非递归顺序完成两轮计算
可以从节点 111 开始,建立一个遍历序列 ord\operatorname{ord}ord。处理序列中的节点时,把它的儿子追加到末尾,同时记录每个节点的父节点和父边长度。这样,父节点一定出现在儿子之前。
逆序处理 ord\operatorname{ord}ord,每个节点的儿子都已经处理完,可以把当前节点的子树大小和子树距离和累加给父节点。
再顺序处理 ord\operatorname{ord}ord,每个节点的父节点答案都已经求出,可以使用换根公式计算当前节点的答案。两轮计算都只处理每条父子关系一次。
当树是一条长度很大的链时,递归深度可能达到 nnn。参考代码使用遍历序列完成上述过程,额外调用栈深度为常数。
数值范围与输出
距离和需要使用足够大的整数类型。考虑 n=200000n=200000n=200000、每条边长为 10910^9109 的一条链。从端点出发,到各点的距离依次为 0,109,2×109,…,(n−1)×1090,10^9,2\times10^9,\ldots,(n-1)\times10^90,109,2×109,…,(n−1)×109,距离总和为
109∑i=0n−1i=109×200000×1999992=19999900000000000000.10^9\sum_{i=0}^{n-1}i =10^9\times\frac{200000\times199999}{2} =19999900000000000000. 109i=0∑n−1 i=109×2200000×199999 =19999900000000000000.
这个值超过有符号 long long 的最大值 922337203685477580792233720368547758079223372036854775807。因此,参考代码使用 __int128 保存 f\operatorname{f}f、ans\operatorname{ans}ans,并在乘法之前转换到 __int128。边权本身使用 long long 保存即可。
printf 没有直接输出 __int128 的格式符,可以不断取十进制末位,把得到的数字逆序后输出。所有答案均为非负整数;当 n=1n=1n=1 时,唯一节点的答案是 000,输出函数也要能处理这一情况。
部分分说明:
* 测试点 1∼51\sim51∼5(n≤1000n\le1000n≤1000):枚举每个起点,分别遍历整棵树,累加从该起点出发的所有距离,总时间复杂度为 O(n2)O(n^2)O(n2)。
* 测试点 6∼106\sim106∼10(特殊性质 A,整棵树是一条链):从端点出发恢复链上节点的顺序,设第 iii 个节点的位置为 xix_ixi ,前缀和为 Pi=∑j=1ixjP_i=\sum_{j=1}^{i}x_jPi =∑j=1i xj ,且 P0=0P_0=0P0 =0。它到左侧节点的距离和为 (i−1)xi−Pi−1(i-1)x_i-P_{i-1}(i−1)xi −Pi−1 ,到右侧节点的距离和为 (Pn−Pi)−(n−i)xi(P_n-P_i)-(n-i)x_i(Pn −Pi )−(n−i)xi ,两部分相加即可。恢复顺序、计算前缀和以及求全部答案的时间复杂度均为
O(n)O(n)O(n),位置前缀和及答案使用 __int128。也可以先求一个端点的答案,再按相邻节点间的距离变化逐点递推。n=1n=1n=1 时直接输出 000。
* 测试点 11∼2011\sim2011∼20(无额外限制):使用完整的换根算法,逆序计算子树大小和子树距离和,再顺序求出所有节点的答案,总时间复杂度为 O(n)O(n)O(n)。
实现步骤
1. 读入树,使用邻接表保存每条无向边的两个方向。
2. 从节点 111 开始生成遍历序列 ord\operatorname{ord}ord,记录每个节点的父节点 fa[u]\operatorname{fa}[u]fa[u] 和父边长度 pw[u]\operatorname{pw}[u]pw[u]。
3. 初始化所有 sz[u]=1\operatorname{sz}[u]=1sz[u]=1、f[u]=0\operatorname{f}[u]=0f[u]=0。
4. 逆序处理序列中除根以外的节点 uuu,令 p=fa[u]p=\operatorname{fa}[u]p=fa[u],将 sz[u]\operatorname{sz}[u]sz[u] 累加到 sz[p]\operatorname{sz}[p]sz[p],将 f[u]+sz[u]×pw[u]\operatorname{f}[u]+\operatorname{sz}[u]\times\operatorname{pw}[u]f[u]+sz[u]×pw[u] 累加到 f[p]\operatorname{f}[p]f[p]。
5. 设置 ans[1]=f[1]\operatorname{ans}[1]=\operatorname{f}[1]ans[1]=f[1]。
6. 顺序处理序列中除根以外的节点 uuu,计算 ans[u]=ans[fa[u]]+(n−2sz[u])×pw[u]\operatorname{ans}[u]=\operatorname{ans}[\operatorname{fa}[u]]+(n-2\operatorname{sz}[u])\times\operatorname{pw}[u]ans[u]=ans[fa[u]]+(n−2sz[u])×pw[u]。
7. 按节点编号从小到大,把每个 __int128 答案转成十进制输出。
正确性证明
首先证明逆序计算得到的子树信息正确。
叶子节点的子树只有它自身,所以初始化的 sz[u]=1\operatorname{sz}[u]=1sz[u]=1、f[u]=0\operatorname{f}[u]=0f[u]=0 正确。对于任意非叶子节点 uuu,逆序处理保证它的全部儿子已经处理完成。不同儿子的子树互不相交,与节点 uuu 自身恰好组成 uuu 的子树,因此大小累加得到正确的 sz[u]\operatorname{sz}[u]sz[u]。对每个儿子 vvv,到它子树内所有节点的距离贡献为 f[v]+sz[v]×wu,v\operatorname{f}[v]+\operatorname{sz}[v]\times
w_{u,v}f[v]+sz[v]×wu,v ,累加后得到正确的 f[u]\operatorname{f}[u]f[u]。由此,全部子树信息正确,ans[1]=f[1]\operatorname{ans}[1]=\operatorname{f}[1]ans[1]=f[1] 也正确。
其次证明换根计算正确。设 ans[p]\operatorname{ans}[p]ans[p] 已经正确,uuu 是 ppp 的儿子。删去边 (p,u)(p,u)(p,u) 后,所有节点被完整地分成 uuu 的子树和子树外两部分。起点由 ppp 移到 uuu 时,这两部分的距离总和分别减少 sz[u]×w\operatorname{sz}[u]\times wsz[u]×w、增加 (n−sz[u])×w(n-\operatorname{sz}[u])\times w(n−sz[u])×w。因此,换根公式准确计算出 ans[u]\operatorname{ans}[u]ans[u]。
顺序遍历中,父节点总在儿子之前。以正确的 ans[1]\operatorname{ans}[1]ans[1] 为起点归纳,全部节点的答案都正确。最终按照节点编号输出,因此算法符合题目要求。
复杂度分析
建立遍历序列时,每条无向边被检查两次;逆序计算和顺序换根各处理 n−1n-1n−1 条父子关系。因此,总时间复杂度为 O(n)O(n)O(n)。
邻接表、遍历序列以及各状态数组占用 O(n)O(n)O(n) 空间。十进制输出的位数有固定上界,不改变上述复杂度。
参考代码
有帮助,赞一个