写一下题解，顺便纪念一下考场上少加一个等号挂 100 分的事实。
比今年简单的 csps 不多了……希望 noip 不要寄成这个狗样。
如果说错了请线下打我。
考虑搬到序列上的做法，即给你 \(w_1,w_2,...,w_n\)，求 \((l,r)\) 中取若干数，构造序列 \(p_1=l,p_m=r,\forall i \in (2,m],p_i-p_{i-1}\le k\)，使得 \(\sum\limits_{i=1}^{m}w_{p_i}\) 最小。
可以直接设 \(dp_i\) 表示到 \(i\) 点的最小答案，显然有 \(dp_i\gets \min\limits_{d=1}^{k}\{dp_{i-d}\}+w_i\)。
这东西能用广义矩阵乘法优化，假如 \(k=3\)：
然后你把这直接搬到树上，大概可以获得 60 分（过掉 \(k=1,2\) ）的点。
显然这个东西是能过 \(k=1\) 的，由于 \(k=2\) 的情况时没有从 \(v\) 跳到 \(u\) 子树再跳回来的情况（因为这样还不如直接跳 \(u\) ……），所以直接拿线段树/倍增维护上述转移矩阵应该都是可行的。
但是 \(k=3\) 时，考虑从 \(v\) 跳到 \(u\) 或 \(u\) 的上面，有两种可能：
- 跳到 \(u\)，再跳到 \(u\) 的上面。
- 跳到 \(v\) 的子树，再跳到 \(u\) 的上面。
你把上面那个 dp 糊了上去，过不了官方给的大样例。
那我们重新定义 \(dp\) 状态：\(dp_{u,0/1/2}\) 表示跑到 \(u\) 的子树内距离 \(u\) 点为 \(0/1/2\) 的最小答案。
那么有下述转移（记 \(v\) 为 \(u\) 的儿子，\(N(u)\) 为 \(u\) 的邻域即 \(\bigcup\{t|(u,t)\in E\}\)）：
- 显然地，\(dp_{u,0}=w_u+\min\{dp_{v,0},dp_{v,1},dp_{v,2}\}\)
- \(dp_{u,1}=\min\{dp_{v,0},dp_{v,1}+\min\limits_{t\in N(u)}w_t\}\)，因为可以从 \(v\) 的儿子直接跳到 \(u\) 的儿子。
- \(dp_{u,2}=dp_{v,1}\)。
上述转移有一个重点：深度大的都不可能从深度小的转移过来，感性理解，因为如果你跳回去了，你必定走反方向，而这样必定不优。
可以预处理 \(mn_u=\min\limits_{t\in N(i)}w_t\)，然后写成矩阵形式：
其实只改了一个元素。
对于询问 \((u,v)\)，让 \(u\) 为深度较大的那个点，然后钦定一开始选 \(u\)，把答案矩阵赋为 \([w_u,∞,∞]\)，然后求 \(fa_u\) 到 \(v\) 上的矩阵积即可。
代码，使用树剖加线段树维护矩阵，通过了洛谷的民间数据和 infOJ 的数据，复杂度 \(O(q\log^2 n)\)。