@[w9095](/user/569235) 最终答案选取 $g_{0,1}$ 和 $g_{1,0}$ 就不对了。为什么是 $g_{1,1}$？为什么 $g_{1,1}$ 存的就是 $f$ 的值？
by w9095 @ 2024-02-18 18:34:20
实际上我根本看不懂。。。
by iqiqiqiqiqiqiqiq @ 2024-02-18 18:45:19
@[iqiqiqiqiqiqiqiq](/user/780774) 不懂可以不说
by Hoks @ 2024-02-19 12:00:30
您应该和我一样，都使用的是如下形式的矩阵：
$$
\begin{bmatrix}
inf&g_{i,0}\\
g_{i,1}&g_{i,1}
\end{bmatrix}
$$
即左上角一个 $inf$，右上角是轻儿子全选，左下、右下均是轻儿子可选可不选的情况。
您可以手模两个点重链的情况：
$$
\begin{bmatrix}
inf&g_{i,0}\\
g_{i,1}&g_{i,1}
\end{bmatrix}
\times
\begin{bmatrix}
inf&g_{j,0}\\
g_{j,1}&g_{j,1}
\end{bmatrix}
$$
按照乘法顺序，显然 $i$ 是根节点，$j$ 是叶节点，那么 $g_{j,0}=0$ 。
结果为：
$$
\begin{bmatrix}
g_{i,0}+g_{j,1}&g_{i,0}+g_{j,1}\\
g_{i,1}+g_{j,1}&\min(g_{i,1}+0,g_{i,1}+g_{j,1})=g_{i,1}+0
\end{bmatrix}
$$
可以发现，由于第二个矩阵 $inf$ 的存在，导致计算时左下角的必选 $i$，不选 $j$ 的情况被 ban 掉了，导致左下角可能会偏大，不一定等于右下角，实际上就是[这个讨论](https://www.luogu.com.cn/discuss/627642)中第 $2$ 点即叶节点（重链末端）的矩阵左上角因特别置为 $0$。实际上他说的另一种解决方案乘上矩阵
$$
\begin{bmatrix}
0\\
0
\end{bmatrix}
$$
就是取了矩阵中的 $g_{0,1},g_{1,1}$。
建议可以通过手模两个点的重链的情况来确定答案的所在位置以及是否需要特判。
by NATO @ 2024-02-22 21:36:06
@[NATO](/user/443649) thx&orz
by w9095 @ 2024-02-23 17:33:20