请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

[USACO23FEB] Fertilizing Pastures G

2023-07-13

洛谷[USACO23FEB] Fertilizing Pastures G

题目大意

有一棵 n n n个点的树,经过每条道路需要花费一秒钟。每过一秒,树上第 i i i个点的权值会增加 a i a_i ai。你需要从结点 1 1 1开始遍历这棵树,在第一次经过一个点时,如果这个点此时的权值为 x x x,则你需要花费 x x x个单位的金额。

还有一个参数 T ∈ { 0 , 1 } T\in\{0,1\} T{0,1}。如果 T = 0 T=0 T=0,则你需要在结点 1 1 1结束;如果 T = 1 T=1 T=1,则你可以在任意结点结束。计算遍历的最短时间以及在最短时间的前提下的最小花费。

2 ≤ n ≤ 2 × 1 0 5 , 1 ≤ a i ≤ 1 0 8 2\leq n\leq 2\times 10^5,1\leq a_i\leq 10^8 2n2×105,1ai108


题解

先考虑 T = 0 T=0 T=0的情况。因为要回到结点 1 1 1,所以每条边都会被经过两次,那么时间就为 2 ( n − 1 ) 2(n-1) 2(n1)

当遍历到一个点时,对于它的两个儿子 v 1 , v 2 v_1,v_2 v1,v2,设它们的子树的 a i a_i ai之和为 s 1 , s 2 s_1,s_2 s1,s2,子树大小为 t 1 , t 2 t_1,t_2 t1,t2,则先进入 v 1 v_1 v1比先进入 v 2 v_2 v2多出的花费为 2 t 1 ⋅ s 2 − 2 t 2 ⋅ s 1 2t_1\cdot s_2-2t_2\cdot s_1 2t1s22t2s1。当 2 t 1 ⋅ s 2 − 2 t 2 ⋅ s 1 < 0 2t_1\cdot s_2-2t_2\cdot s_1<0 2t1s22t2s1<0时,先进入 v 1 v_1 v1会更优。整理一下,即 t 1 s 1 < t 2 s 2 \dfrac{t_1}{s_1}<\dfrac{t_2}{s_2} s1t1<s2t2时先进入 t 1 t_1 t1会更优。那么,我们可以按 t s \dfrac ts st从小到大对每个点进行排序,越靠前的优先度越高。按这个优先度遍历一次并计算花费,即可得到答案。

接下来,我们来考虑 T = 1 T=1 T=1时的情况。因为可以在任意结点结束,所以我们要将结束点选在离结点 1 1 1最远的位置,来保证时间最短。设结点 1 1 1与结束点的距离为 m x d mxd mxd,则时间为 2 ( n − 1 ) − m x d 2(n-1)-mxd 2(n1)mxd

c 1 i c1_i c1i表示在 i i i的子树中不需要选结束点时,以遍历到结点 i i i为第 0 0 0时刻,遍历完 i i i的子树所需的花费; c 2 i c2_i c2i表示在 i i i的子树中需要选结束点时,以遍历到结点 i i i为第 0 0 0时刻,遍历完 i i i的子树所需的花费。用 T = 0 T=0 T=0时的思路就可以求出 c 1 i c1_i c1i。对于 c 2 i c2_i c2i,我们可以基于 c 1 i c1_i c1i来求出。

对于结点 i i i,计算 c 1 i c1_i c1i时是按其 t s \dfrac ts st从小到大来遍历的。在计算 c 2 i c2_i c2i时,我们先按 t s \dfrac ts st i i i的儿子进行排序,再分别考虑存在结束点的儿子。若结束点要设在儿子 v v v中,设 s v , t v s_v,t_v sv,tv表示 v v v的子树的 a i a_i ai之和以及 v v v的子树大小, S , T S,T S,T表示排在 v v v之后的点的子树的 a i a_i ai之和以及这些点的子树大小的和。那么, v v v设为结束点之后, c 2 i c2_i c2i相对于 c 1 i c1_i c1i来说增加了 T ⋅ s v − S ⋅ t v + c 2 v − c 1 v T\cdot s_v-S\cdot t_v+c2_v-c1_v Tsv

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部