思路与算法

先考虑s到t的树上简单路径。权值全为正，最优转发链可按其在此路径的投影顺序前进。k≤2时只需选路径点；k=3时还可能选某路径点旁一条边处的便宜点。记v_i为路径点权，c_i为它所有邻点的最小权。路径邻点也可纳入c_i，三角不等式保证这种保守距离模型生成的转发仍合法，且真正旁支候选全部包含。 沿路径维护三个状态：最后一个所选转发点距当前前沿为0、1、2时的最小代价。前沿从i-1移到i，k=3转移为 f'_0=v_i+min(f_0,f_1,f_2)，f'_1=min(f_0,c_i+f_1)，f'_2=f_1。也就是min-plus矩阵[[v,v,v],[0,c,∞],[∞,0,∞]]乘状态列向量。选旁支点只有在旧距离≤1时合法；旧距离0的旁支选择被不选任何新点的f_0支配，故只保留c_i+f_1。k=2截取左上2×2、k=1只剩[v]。 树链剖分把查询路径拆成有方向的连续编号区间。线段树同时保存各区间从左向右和从右向左的矩阵积。查询初始化为(v_s,∞,∞)，跳过首点矩阵，依路径顺序对状态应用各区间矩阵，最终取状态0，强制t也被选。

正确性说明

先规范化转发链。对于连接在主路径点p上的一个旁支，取链进入该旁支到最后离开的整段。两端在旁支外，若入口或出口使用的旁支点深度至少2，k≤3使其外侧点到p距离至多1，另一侧至多2，外侧两点可以直接相连并删掉这次旁支绕行。否则入口和出口都只能是p的同一直接邻点，保留它一次、删除中间绕行即可。因此深度至少2的旁支点全部可去掉，k≤2时连深度1旁支也不需要。 余下点到主路径的距离只能为0或1。若三个连续投影形成严格局部极大或极小，中间点到两侧的整数间距至少1，足以补偿两侧离路径高度差至多1，所以两侧距离不大于原来两条边的最大值，可以直接相连并删中间点。同投影的连续段先去掉多余点：有路径点时它到外部总不比旁支点远，没有路径点时保留最低费用旁支点。于是反复消去投影回退，得到按s至t投影单调的链，代价不增。 对这样的规范链，选路径点时旧距离加1≤k，选旁支时旧距离加2≤3，正好是转移列出的选择。保留到前沿距离1的旧路径点不付新代价，支配从距离0旧状态另选旁支的方案，删去这条被支配转移不影响最优。归纳三状态涵盖所有规范链且每个转移都可实现。端点初始化和取状态0保证两端费用都计入。min-plus乘法满足结合律，区间矩阵依次应用与逐点DP相同；双向矩阵与树链区间拼接恰按s至t次序，故得到全局最小转发代价。

复杂度

扫描邻边求c、迭代求父子序与重链编号O(n)，建线段树O(nk³)，空间O(nk²+n)。一条树路径拆O(log n)重链，每段访问O(log n)线段树结点，对状态的应用O(k²)，每询问O(k²log²n)，总O(nk³+Qk²log²n)，k≤3。没有深树递归遍历，线段树也用迭代构建与查询。

易错点

k=3只在主路径做三步DP会漏掉便宜旁支。矩阵乘法不交换，反向区间不能沿正序使用。终点必须作为转发点计费；距离是树的边数，单点处理时间是点权。总答案可达2×10^14，需64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4000000000000000000LL;
int K;
struct Mat {
    ll a[3][3];
    Mat(bool identity = false) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                a[i][j] = (identity && i == j ? 0 : INF);
    }
};
Mat mul(const Mat &a, const Mat &b) {
    Mat z;
    for (int i = 0; i < K; i++)
        for (int j = 0; j < K; j++)
            for (int t = 0; t < K; t++)
                z.a[i][j] = min(z.a[i][j], a.a[i][t] + b.a[t][j]);
    return z;
}
void apply(const Mat &a, array<ll, 3> &v) {
    array<ll, 3> w = {INF, INF, INF};
    for (int i = 0; i < K; i++)
        for (int j = 0; j < K; j++)
            w[i] = min(w[i], a.a[i][j] + v[j]);
    v = w;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q >> K;
    vector<ll> value(n + 1), cheap(n + 1, INF);
    for (int i = 1; i <= n; i++)
        cin >> value[i];
    vector<vector<int>> adj(n + 1);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        cheap[u] = min(cheap[u], value[v]);
        cheap[v] = min(cheap[v], value[u]);
    }
    vector<int> parent(n + 1), depth(n + 1), size(n + 1, 1), heavy(n + 1), order{1};
    size[0] = 0;
    for (size_t i = 0; i < order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != parent[u]) {
                parent[v] = u;
                depth[v] = depth[u] + 1;
                order.push_back(v);
            }
    }
    for (int i = n - 1; i > 0; i--) {
        int u = order[i], p = parent[u];
        size[p] += size[u];
        if (size[u] > size[heavy[p]])
            heavy[p] = u;
    }
    vector<int> head(n + 1), pos(n + 1), at(n);
    int timer = 0;
    vector<pair<int, int>> todo{{1, 1}};
    while (!todo.empty()) {
        auto a = todo.back();
        todo.pop_back();
        for (int u = a.first; u; u = heavy[u]) {
            head[u] = a.second;
            pos[u] = timer;
            at[timer++] = u;
            for (int v : adj[u])
                if (parent[v] == u && v != heavy[u])
                    todo.push_back({v, v});
        }
    }
    int S = 1;
    while (S < n)
        S *= 2;
    vector<Mat> f(2 * S, Mat(true)), b(2 * S, Mat(true));
    for (int i = 0; i < n; i++) {
        int u = at[i];
        Mat m;
        for (int j = 0; j < K; j++)
            m.a[0][j] = value[u];
        for (int j = 1; j < K; j++)
            m.a[j][j - 1] = 0;
        if (K == 3)
            m.a[1][1] = cheap[u];
        f[S + i] = b[S + i] = m;
    }
    for (int i = S - 1; i; i--) {
        f[i] = mul(f[i * 2 + 1], f[i * 2]);
        b[i] = mul(b[i * 2], b[i * 2 + 1]);
    }
    auto rangeApply = [&](int l, int r, bool reverse, array<ll, 3> &state) {
        vector<int> left, right;
        for (l += S, r += S + 1; l < r; l /= 2, r /= 2) {
            if (l & 1)
                left.push_back(l++);
            if (r & 1)
                right.push_back(--r);
        }
        if (!reverse) {
            for (int x : left)
                apply(f[x], state);
            for (auto it = right.rbegin(); it != right.rend(); it++)
                apply(f[*it], state);
        } else {
            for (int x : right)
                apply(b[x], state);
            for (auto it = left.rbegin(); it != left.rend(); it++)
                apply(b[*it], state);
        }
    };
    while (q--) {
        int s, t;
        cin >> s >> t;
        array<ll, 3> state = {value[s], INF, INF};
        bool first = true;
        auto go = [&](int l, int r, bool reverse) {
            if (first) {
                if (reverse)
                    --r;
                else
                    ++l;
                first = false;
            }
            if (l <= r)
                rangeApply(l, r, reverse, state);
        };
        vector<pair<int, int>> tail;
        int u = s, v = t;
        while (head[u] != head[v]) {
            if (depth[head[u]] >= depth[head[v]]) {
                go(pos[head[u]], pos[u], true);
                u = parent[head[u]];
            } else {
                tail.push_back({pos[head[v]], pos[v]});
                v = parent[head[v]];
            }
        }
        if (depth[u] >= depth[v])
            go(pos[v], pos[u], true);
        else
            go(pos[u], pos[v], false);
        for (auto it = tail.rbegin(); it != tail.rend(); it++)
            go(it->first, it->second, false);
        cout << state[0] << '\n';
    }
}