Solution
根据一些逝去的记忆可以得到一个 DP 状态：\(f_{u,x,y}\) 表示 \(u\) 这棵子树，\(x\) 从子树出去，\(y\) 进来这棵子树。然后讨论一下状态转移，可以暴力枚举状态，暴力枚举之后发现一件事情，\(u,ls,rs\) 三个状态中至少一个包含 \(u\)，然后可以想到枚举三条边的执行顺序，这样子状态转移是确定的，可以得到 \(6\) 种转移。状态优化比较困难。
事实上这种较为基本的 DP 转移讨论状态优化，首先需要把 DP 写成基本形式，也就是刷表法，这种形式的 DP 方程比较易于考虑优化。
首先右儿子为空的情况：
\[f_{u,u,i}=\min_j(f_{ls,j,i})+d_u+d_i \]\[f_{u,j,i}=f_{ls,j,u}+d_j+d_i \]然后是左右儿子都非空的情况：
\[f_{u,u,i}=\min_{j}(f_{ls,j,i}+\min_{k}f_{rs,k,j})+d_u+d_i \]\[f_{u,j,i}=f_{ls,j,u}+\min_k f_{rs,k,i}+d_j+d_i \]\[f_{u,j,i}=\min_{k}(f_{ls,k,u}+f_{rs,j,k})+d_j+d_i \]对称的转移被省略。
如果仔细观察上述转移形式，可以发现所有的 \(f\) 值实际上可以被 \(\mathcal{O}(n^2)\) 个状态生成出来，即：
- \(A_{u,i}=f_{u,j,fa_u}\)。
- \(B_{u,i}=\min\limits_{j}(f_{ls,j,i}+\min_{k}f_{rs,k,j})\)。
- \(C_{u,i}=\min_j f_{u,j,i}\)。
- \(D_{u,i}=\min_k(f_{ls,k,u}+f_{rs,i,k})\)。
做一些工作就可以把 \(f\) 表示出来，此时我们只要讨论怎么将转移优化到 \(\mathcal{O}(n^2)\) 即可。
精细分析一下，对于 \(A\) 的求解，显然是对的。对于 \(D\) 的求解，我们只需要枚举右子树的 \(i\) 和左子树的 \(j\) 可以做到 \(\sum sz_{ls}sz_{rs}\) 的复杂度，这个复杂度是 \(\mathcal{O}(n^2)\) 的，只需要讨论 \(B,C\) 的转移即可，而这两个转移的思路是类似的，以 \(C\) 为例。
不妨假设 \(u\) 的左右儿子是全的，将 \(f_{u,j,i}\) 展开：
\[C_{u,i}=\min_j(f_{ls,j,u}+C_{rs,i}+d_j+d_i) \]\[C_{u,i}=\min_j(D_{u,i}+d_i+d_j) \]将所有不含 \(j\) 的项分离除去，发现 \(C_{u,i}\) 变成了关于 \(i\) 的函数，可以线性转移。
另外一种方式也是通过精细分析得到状态数量正确。分析我们当前的状态数是 \(\sum sz_x(n-sz_x)\)，考虑转化状态，一个直觉是 \(y\) 这一维并不是很重要，只需要在得到 \(y\) 的时候直接计算贡献即可，所以可以得到一个这样的状态：\(f_{u,x,i}\) 表示 \(x\) 出去，\(y\) 的贡献为 \(i\) 的答案。粗略分析可以得到一个 \(\sum sz_x^2\) 的界，看起来不是很优秀，但是发现 \(x\) 出去，\(i\) 的贡献不会超过 \(x\) 的另一边子树，于是可以分析到 \(\sum sz_{ls}sz_{rs}\) 的级别。这是是平方的。
Conclusion
神题，整个过程分析曲折又不失逻辑性，用基础的分析技巧最后得到一个相当困难的问题。分步讨论这题的关键。
- 状态设计。观察答案的构成形态可以发现，每个点的贡献是它经过的路径长度，考虑路径形态，发现每条边只会被上下经过恰好两次。套路地以子树阶段定义状态，可以发现子树与外界的联系其实相当少，钦定父亲边的贡献构成可以得到一个三方状态。
- 状态优化。这里用到了一个更为基础也不是很常见的优化方法。首先将状态转移写成填表的基本形式方便分析，然后观察状态实际上可以被更少的状态表示。
- 转移优化，展开状态式子，优化转移。
其中状态的定义是需要灵感的，后面的过程则较为基础，而基础的部分恰是本题最重要的一部分。本题隐藏在 DP 转移中的性质较为复杂，但关键在于，我们对于状态转移的过程建立了形式直观，也就是使用了恰当的公式刻画它。性质的观察并不只在于直觉与证明，还有建立直观与分析。
本题的另一个做法则较为复杂，将状态转化为另一个复杂度形式不同的等价形式，通过精细分析得到正确的复杂度，现在应该学会脱离依赖直觉的分析方式，多动笔去精细分析。
标签：状态,P8294,min,题解,rs,转移,sz,ls,联考 From： https://www.cnblogs.com/yllcm/p/17049069.html