南外集训 2024.2.14 T3

总觉得做过，但是就是想不起来在哪里做到的。

有两个人一开始在一棵树的根节点，每秒钟两人都可以向下走一条边。任意时刻，一个人可以瞬间移动到另一个人所在的点上。求遍历树上的所有点所需最短时间。

\(1\le n\le 5\times 10^6\)

注意到我们只需要访问所有的叶子。我们把其中一个人叫人，另一个叫影子。

一个错误的想法：考虑一种状态设计：两个人同时在 \(u\)，且 \(u\) 子树外的所有点都被访问过，\(u\) 子树内只有 \(u\) 呗访问过。那么此时的策略（似乎）应该是留下一棵子树不动它，然后影子不停地下去处理其他子树里的叶子，直到只剩一个最深的，然后人不停往被保留的子树走，直到第一个有分叉的位置，同时影子向最后一个叶子走。两个人都走到目的地以后，影子瞬间移动回到人，转移到子问题。

这个想法是错误的，而且实际上是很不自然的：假设当前节点只有两个儿子，其中各有一个非常深的叶子，以及一系列很浅的叶子，那么正确的策略是保留两个最深的叶子，人一直不动，影子把所有浅叶子处理掉以后两人同时往两个深叶子走。而我们上面的策略实际上限制了进入一棵子树的时候必须要清理掉所有外面的叶子，只有子树上面的一小段单个儿子的链可以和外面的并行处理，而这是非常不自然的，并不能真正起到并行减少时间的效果，因为很容易通过在每个点旁边挂一些浅叶子来消除掉这种单个儿子的链，而直觉告诉我们最优解的策略不应该受此影响。

我们重新考虑整个问题。事实上我们并不是在一棵子树一棵子树地解决问题，而是通过每次确定一个特殊的子树并进入的过程，确定了一个特殊的根-叶子链，具体地也就是上面过程中人（而不是影子）所走的路径。每个不在这条链上的叶子都需要由影子在某个时刻出发去清理掉。假设已经选定了这个路径，我们可以将最小化总时间转化为最小化人等待影子的时间，进一步地，如果影子等待人，那么我们可以强制将它传送回来跟着人走。这样，我们只需要决定路径上的一系列关键点，在这些关键点，人等待影子清理一些叶子。影子每次会清理一个叶子，回到人，再清理，……，直到所有从这个关键点出发的叶子只剩最后一个（最优解中一定是最深的那个），此时人就开始向下走，且影子清理完这个叶子之前，人必须已经走到下一个关键点。那么注意到此时总时间实际上就是影子清理叶子的总时间，即所有被清理的叶子的深度和减去关键点的（带权）深度和，因为人永远在等待影子。

下面考虑一个 \(\Theta(n^2)\) 的 DP。设 \(f_u\) 表示走到点 \(u\) 时，最少已经花费的时间，转移直接在 \(u\) 到根的链上枚举上一个关键点 \(v\)，设 \(S_x\) 表示 \(x\) 子树内所有叶子的集合。\(sum(S_x)\) 表示 \(S_x\) 的深度和；\(mxd(S_x)\) 表示 \(S_x\) 的深度最大值，则转移合法当且仅当：\(mxd(S_v\backslash S_u) - dep_v \ge dep_u - dep_v\)，转移为 \(f_v + sum(S_v\backslash S_u) - |S_v\backslash S_u|\cdot dep_v \to f_u\)。此外特判一下父节点只有一个儿子可以直接转移过来。

由于 \(S_v\backslash S_u\) 可以拆分成 \(path(v,u)\backslash\{v\}\) 的“兄弟子树信息”的并，结合上面的式子我们发现，对于一个 \(u\)，根到它的链上的一个前缀都是合法的。又注意到，在合法的前提下，转移的时间越晚越好。这是因为在某个合法解中，不影响合法性地插入一个关键点，会使得链外的叶子更容易匹配到离它更近的关键点，从而使答案更优。除此之外，如果在 \(u\) 可以从 \(v\) 转移过来，那么 \(path(v, u)\) 上的每个点都可以从 \(v\) 转移过来。所以我们只关心最后一个合法转移位置。利用重链剖分进行寻找及转移，容易获得 \(\Theta(n\log n)\) 做法。

注意到在上面的问题中我们使用了重链剖分，而转移合法性是深度相关信息，这简直倒反天罡。把重链剖分换成长链剖分，发现如果我们在向上寻找的过程中跳了长链，此时走到的第一个位置一定已经是合法转移了，于是不用再往上考虑。没跳长链的部分直接用单调栈。复杂度 \(\Theta(n)\)。

我草，卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼卡常傻逼。