更好的阅读体验

补充：这个解法是我自己的，相当麻烦，有比我简洁的 DP 做法，还有 dottle 老师的神奇最短路做法，推荐去洛谷题解看看。

首先，看到 $k\le 3$ 的范围，显然是要分类讨论。

k=1

显然，最小花费即为 $u\to v$ 在树上路径的点权和。倍增预处理，每次查询 LCA 然后树上前缀和即可。

时间复杂度 $\mathcal O((n+m)\log n)$。

k=2

先考虑暴力的做法。将 $u\to v$ 在树上的路径拆下来，将点权写作序列 $b_{1\sim p}$ 研究。

我们用动态规划解决这个问题。设 $f(i)$ 表示 $1\sim i$ 的最小花费。

初始状态：$f(1)=b_1$。

状态转移方程：$f(i)=\min\{f(i-1)+b_i,f(i-2)+b_i\}$。

如果对矩阵很熟悉，不难发现这个就是一个矩阵优化的板子。

不过此处 $b_i$ 是变量，无法进行矩阵快速幂，当时考场上想到这里我脑子莫名其妙宕机了，感觉这题正解绝对是矩阵，但这个东西不会处理啊，然后就彻底蒙了，完全想偏了，最后打了暴力。

实际上和快速幂没有任何关系。因为是树上的静态查询问题，自然可以往倍增想。

因为矩阵满足交换律和结合律，完全可以把矩阵先存起来预处理，最后查询的时候再一次倍增求解。

先把上面那个式子写成矩阵：

$$\begin{bmatrix}f(i-1) & f(i-2)\end{bmatrix}\times\begin{bmatrix}a_i & 0\\a_i & +\infty\end{bmatrix}=\begin{bmatrix}f(i) & f(i-1)\end{bmatrix}$$

为了方便，我们定义 $t=\text{LCA}(u,v)$，$k=3$ 时亦然。

把中间的转移矩阵存起来倍增预处理一下，询问的时候，因为正着走和倒着走没有区别，我们把 $u\to t\to v$ 拆成 $u\to t,v\to t$ 两条链，以 $u\to t$ 为例：

初始向量矩阵：

$$\begin{bmatrix}a_u & +\infty \end{bmatrix}$$

然后把 $fa_u\to t$ 上的转移矩阵全乘起来，就得到了 $u\to t$ 这条链上的答案。

类似地处理 $v\to t$，接下来考虑合并答案。

因为 $k=2$，只有两种可能：$u$ 走到 $t$ 再走到 $v$，或者不经过 $t$，直接从 $t$ 在 $u\to v$ 路径上的两个子节点处穿过。

记 $u\to t$ 的矩阵为 $P$，$v\to t$ 的矩阵为 $Q$，因为可以写作一维向量的形式，为了方便，我们直接将 $P$ 中的元素用类似序列下标的形式表示，即 $P(0),P(1)$。下面 $k=3$ 的情况里我们仍采用这种称呼。

针对两种情况，答案分别为 $P(0)+Q(0)-a_t,P(1)+Q(1)$，两者取 $\text{min}$ 即可。

时空复杂度 $\mathcal O(2^3\times (n+m)\log n)$。

k=3

其实 $k=3$ 大体思路和 $k=2$ 完全一致，只不过有一个小细节：答案路径上的节点不一定都是 $u\to v$ 这条链上的。

原因很简单，比如链上的点权都是 $10^9$ 级别，而与链相连的节点中有一个点权是 1，那走这个点显然更优。

题解里大部分做法是将距离设入状态中，我当时并没有想到，而是直接把链接出去的点再设计一个方程。

还是先考虑一条链上的暴力，因为与 $u$ 相连的点中，只有点权最小的有效，设这个最小点权为 $c_u$。

在 $k=2$ 的情况上再加一条：设 $g(i)$ 表示走到 $i$ 连接的点上的最小路径花费。

状态转移方程：

$$f(i)=\min\{f(i-1)+a_i,f(i-2)+a_i,f(i-3)+a_i,g(i-1)+a_i,g(i-2)+a_i\}\\g(i)=\min\{f(i-1)+c_i,f(i-2)+c_i,g(i-1)+c_i\}$$

考虑将这个东西写成矩阵，那么样子就长这样：

$$\begin{bmatrix}f(i-1) & f(i-2) & f(i-3) & g(i-1) & g(i-2)\end{bmatrix}\times \begin{bmatrix}a_i & 0 & +\infty & b_i & +\infty\\a_i & +\infty & 0 & b_i & +\infty\\a_i & +\infty & +\infty & +\infty & +\infty\\a_i & +\infty & +\infty & b_i & 0\\a_i & +\infty & +\infty & +\infty & +\infty\end{bmatrix}\\=\begin{bmatrix}f(i) & f(i-1) & f(i - 2) & g(i) & g(i-1)\end{bmatrix}$$

倍增预处理和查询就很类似了，略过。

最后的合并情况很多，这里我直接把所有情况对应的式子列出来，因为用文字真的很难写出来 QAQ，理解一下叭 awa，有兴趣可以自己推一下，如果实在嫌我的方法麻烦还是看别的大佬的题解吧 qwq：

$P(0)+Q(0)-a_t$

$P(3)+ Q(3)-c_t$

$P(1)+Q(1)$

$P(1)+Q(2)$

$P(1)+Q(4)$

$P(4)+Q(1)$

$P(2)+Q(1)$

所有情况取 $\text{min}$ 即可。时间复杂度 $\mathcal O(5^3\times (n+m)\log n)$。