[ABC369G] As far as possible 讲解

zrl123456 · 2024-09-01 19:18:59 · 题解

有人吐槽我题解太水了，这次我就写多点。

[ABC369G] As far as possible

题目考察：图论，长链剖分。
题目简述：
给你一棵 n 个点的带权的树，n 次询问，第 i 次询问要求找出序列 \{x_{i+2}\}，该序列要满足以下条件：

问对于所有的序列中，\displaystyle\sum_{j=1}^{i+1}\text{dist}(x_j,x_{j+1}) 最大是多少。
其中，\text{dist}(a,b) 代表 a 点到 b 点的最短距离。
数据范围：

• 2\le n\le 2\times 10^5
• \forall i\in[1,n-1],1\le u_i,v_i\le n
• \forall i\in[1,n-1],1\le w_i\le 10^9

  设树中有 num 个叶子结点，答案序列为 \{ans_n\}，则对于 i\in[1,n]，ans_i 有以下两种情况：

• 简单证明：若有一个不选叶子结点，则选它的子节点必然更优。
• 简单证明：对于任意一个非叶子结点，选他的子树内的叶子节点的返回（或进入）的时候顺路就把他选了。

那么我们贪心的想，对于某个值最大的肯定要先选，那么这个某个值是什么值呢？
肯定不是深度，因为我们去到那个点不一定要回到 1 号点。
深度不行，那相对某个点的深度呢？
这个是可以的，但复杂度过高。（因为你不知道某个点是哪个点）
最终我们定义 dep_x 如下：

• 若 x 点被遍历，则 dep_x=0。
• 否则设其父节点为 fa，则 dep_x=dep_{fa}+\text{dist}(x,fa)。

但是这样定义就无法知道所有点与它的距离了，所以我们尝试反向定义：dep_x 代表他所在的子树内离他最远的点与他的距离，转移方程为：（设 s_x 为 x 点的儿子集合）：

这样就知道最大的点与他的距离了，而且由于上述的贪心策略，dep_x 最大的肯定最先走，设 son_x 为抵达 x 点后最先走的点，那么不是他的父节点 fa 的 son_{fa} 的点 x 肯定在他遍历完父节点 fa 的 son_{fa} 后还没遍历他 （废话），则他能贡献 dep_x+\text{dist}(x,fa)。

这样这个题就做完了，时间复杂度为 \Theta(n)。
代码