本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-01 19:18:59

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

[ABC369G] As far as possible

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

• $\forall j\in[3,i+1],k\in[2,j-1],x_j\ne x_k$。
• $x_1=x_{i+2}=1$。

问对于所有的序列中，$\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$ 有以下两种情况：

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

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

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

但是这样定义就无法知道所有点与它的距离了，所以我们尝试反向定义：$dep_x$ 代表他所在的子树内离他最远的点与他的距离，转移方程为：（设 $s_x$ 为 $x$ 点的儿子集合）： $$dep_x=\max_{y\in s_x}(dep_y+\text{dist}(x,y))$$ 这样就知道最大的点与他的距离了，而且由于上述的贪心策略，$dep_x$ 最大的肯定最先走，设 $son_x$ 为抵达 $x$ 点后最先走的点，那么不是他的父节点 $fa$ 的 $son_{fa}$ 的点 $x$ 肯定在他遍历完父节点 $fa$ 的 $son_{fa}$ 后还没遍历他 （废话），则他能贡献 $dep_x+\text{dist}(x,fa)$。

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