给定一棵树，树上的一些点被打上了标记，定义一个节点的贡献为其到所有标记节点距离的最大值，求最小贡献。
\(n \le 2 \times 10^5\)。
这道题的原题是 CF337D（甚至要更困难一些）。
很套路的换根 DP 啊。我们考虑设 \(f_i\) 为 \(i\) 子树内的标记节点到 \(i\) 的最大距离，\(g_i\) 为子树外到 \(i\) 的最大距离。首先，\(f\) 的转移是显然的：
\[f_i = \max_{j \in \operatorname{subtree}(i)} \left\{ f_j + 1 \right\} \]直接从子树中转移，取最大值即可。
再来考虑 \(g\) 的转移。我们设 \(fa_i\) 为 \(i\) 的父亲，那么 \(i\) 子树外的点可划分为两个部分：\(fa_i\) 子树外的点与 \(fa_i\) 子树中去掉 \(i\) 的子树的部分。其中 \(fa_i\) 子树外的点的贡献显然就是 \(g_{fa_i} + 1\)，而剩余部分的贡献也不难看出是其子树内部的最大距离再加上它与 \(i\) 的距离，后者显然为 \(2\)。
那么可以得到 \(g\) 的转移方程：
\[g_i = \max \left\{ g_{fa_i} + 1, \max_{j \in \operatorname{subtree}(fa_i) \land j \not= i} \left\{ f_j + 2 \right\} \right\} \]最后是一些转移方面的问题。对于 \(f\) 那没有什么好说的，直接自底向上转移就完事了。对于 \(g\)，一种朴素的转移方法是直接枚举 \(fa_i\) 的所有儿子然后转移，但是这样转移的复杂度是不对的，考虑一个菊花图，那么我们会发现每个点被枚举到的次数为 \(\mathcal{O}(n)\) 的，那么总的时间复杂度会变成 \(\mathcal{O}(n^2)\)，这当然无法接受。一种更聪明的转移方法是在计算 \(f\) 时同时记录下每个点 \(f\) 最大与次大的儿子，那么在转移 \(g\) 时，如果当前点是其父亲的最大的儿子，我们就从次大的儿子转移，否则就从最大的儿子转移，这样转移就是 \(\mathcal{O}(1)\) 的了。
当然，这个题的初始化也要小心，要注意特别考虑被标记的点。那么总体的时空复杂度都为 \(\mathcal{O}(n)\)。
由于比赛没有打，所以代码也没写。不过实现方面也没有什么难度，相信聪明的你一定能写出来的。
标签：Distance,right,复杂度,Maximum,fa,Minimum,子树外,mathcal,转移 From： https://www.cnblogs.com/forgot-dream/p/17761619.html