$\texttt{NOI 2023 T1}$,感觉很复杂的一道题,思维强度远超我的想象。大概想了一个半小时。
首先探究 $x, y$ 在图中的最短路如何去求。很显然,如果 $y$ 是 $x$ 的祖先,问题是平凡的。只需要一直走根向边即可。
接下来讨论,对于 $x, y$ 没有父子关系的情况。设 $z = lca(x, y)$,显然路径分为 $x \rightarrow z \rightarrow y$。对于 $x \rightarrow z$,和刚才讨论的情况一样,直接走根向边即可。问题变为求形如 $z \rightarrow y$ 路径的最短路。
所以将问题转化后形式化一下:
求所有形如 $z \rightarrow y$ 路径的最短路,其中 $z$ 是 $y$ 的祖先。
发现这种路径实际也有讨论的余地。
我们发现,从 $z$ 出发,必定是先走根向边,再走叶向边,到达 $z$ 在 $y$ 方向上的子树。
然后发现,这个问题变成一个等价子问题,可以递归去求解。我们不妨将这个过程记忆化。换言之,设 $f_{z, y}$ 表示从 $z$ 出发,走到 $y$ 的最短路($z$ 是 $y$ 祖先),则有如下转移:
$$f_{z, y} = \max_{a \in \text{fa}(z), x \in \text{path}(z \rightarrow y)}\{ f_{x, y} + w(z \rightarrow x)\}$$
发现 $z$ 在某个方向的路径非常难处理,不妨转化一下状态,将状态的两维倒过来:$f_{y, d}$ 表示 $y$ 的 $d$ 级祖先 $z$ 到 $y$ 的最短路。这样问题得到进一步简化。
于是我们可以 dp 一遍求出 $f$,这部分需要 $O(n ^ 2 2 ^ n)$。接下来,再进行树形 dp,枚举 LCA 计算价值和即可。
草是 $O(n ^ 3 2 ^ n)$ 的。