题解说明

问题描述：
给定一棵有 $n$ 个节点的树和 $q$ 个查询，每个查询给出两点 $(x,y)$。每个节点 $i$ 有一个权值 $a[i]$，并且对每个节点还预处理了 $a[i][1] = \min(\text{相邻节点的 } a[\text{邻居}][0])$。根据参数 $K$（取 $1,2,3$），需要计算从 $x$ 到 $y$ 的路径上，遵循不同状态与转移规则的最小代价，并输出每个查询的答案。

关键思想：
$1.$ 将树上的路径代价计算抽象为“最短路径状态转移”的问题。根据 $K$ 的不同，定义节点的状态数与允许的转移。
$2.$ 使用 DFS $+$ 离线 LCA（通过并查集的路径压缩）在一次遍历中处理所有查询：

• 每个节点 $u$ 挂有以 $u$ 为端点的查询，遍历到一个端点时，如果另一个端点已被并查集“激活”，即可找到 LCA 并把该查询归到 LCA 处延迟计算。
  $3.$ 用“最小值加法半环”的矩阵表示路径段的状态转移：
• 向父合并的过程中，把子到父的转移矩阵乘到并查集代表上，从而在 $findRoot$ 的路径压缩中累积整段的转移效果。
• 查询时为端点 $x,y$ 构建起始向量，分别乘以其到 LCA 的转移矩阵，最后按规则组合得到答案。

状态与转移（按 $K$ 分类）：
$K=1$（单状态，纯加和路径）：

• 定义 $a[u][1]$ 为到根的累积和（父的 $a[1] +$ 自身 $a[0]$）。
• 对查询 $(x,y)$，答案为：

$$ans = sum(x \to root) + sum(y \to root) - 2 \cdot sum(lca \to root) + a[lca][0] $$

• 通过 DFS 直接维护 parent 并用并查集找 LCA，$O(1)$ 时间求解该式。

$K=2$（两状态，简单二态转移）：

• 每个节点有两种状态（可理解为“选自身权值 $a[u][0]$，或选与父相关的替代”），用 $2 \times 2$ 矩阵 $g[u]$ 描述从 $u$ 到父的转移。
• $initMatrix(v,u)$ 构建 $v \to u$ 的矩阵，$findRoot$ 路径压缩时把 $g[x]$ 乘上父的矩阵，实现段转移累计。
• 查询时：
  • 端点 $x$ 的起始向量 $vecX = [a[x][0], INF]$，乘以 $x \to LCA$ 的转移矩阵（若 $x \neq LCA$）
  • 端点 $y$ 同理得到 $vecY$
  • 组合答案：
  $$ans = \min\big( vecX[0] + vecY[0] - a[LCA][0],\ vecX[1] + vecY[1] \big) $$

$K=3$（三状态，扩展态转移）：

• 引入 $3$ 个状态，矩阵 $g[u]$ 为 $3 \times 3$，$initMatrix$ 根据父的 $a[][0/1]$ 构建。
• $findRoot$ 同样在路径压缩时进行矩阵相乘累积。
• 查询时：
  • $vecX = [a[x][0], INF, INF]$ 并乘以 $x \to LCA$ 的矩阵
  • $vecY$ 同理
  • 组合：
  $$ans = \min\Big( vecX[0] + vecY[0] - a[LCA][0],\ vecX[1] + vecY[1],\ vecX[1] + vecY[2],\ vecX[2] + vecY[1] \Big) $$

算法流程：
$1.$ 读入 $n,q,K$；为每个节点读入 $a[i][0]$，并初始化 $a[i][1]=INF$。
$2.$ 读入树边 $(x,y)$，更新两端的 $a[][1] = \min(a[][1], \text{对方的 } a[][0])$，并建邻接表。
$3.$ 把查询 $(x,y)$ 双向挂到 $queryLast$。
$4.$ 若 $K=1$：

• DFS 从 $1$ 出发，维护 $a[u][1]$ 为根路径和，同时用并查集处理查询，直接计算答案式。
  $5.$ 若 $K=2$ 或 $K=3$：
• 清空挂在每个 LCA 的待处理列表 $pendingLast$。
• DFS：
  • 激活 $u$（$parent[u]=u$）
  • 把以 $u$ 为端点的查询，如果另一个端点 $v$ 已激活，则找到 LCA，把该查询挂到该 LCA 的待处理链上
  • 递归子 $v$，回溯时设置 $parent[v]=u$，并初始化 $v \to u$ 的矩阵
  • 在 $u$ 处处理挂在 $u$ 的查询：$findRoot$ 压缩累积矩阵，构造端点向量并乘矩阵，组合得到答案
    $6.$ 输出所有查询答案（使用写缓冲加速）。

复杂度分析：

• 建图与读取：$O(n+q)$
• 单次 DFS：$O(n)$
• 并查集 $+$ 路径压缩 $+$ 矩阵乘法：
  • 每条边、每次 $findRoot$ 至多引起常数次矩阵乘（$2 \times 2$ 或 $3 \times 3$，常数开销）
  • 查询整体仍为近线性
• 总复杂度约 $O(n+q)$，常数因矩阵大小而异，但在题目规模内可接受。

实现细节与注意点：

• $a[i][1]$ 初始化为 $INF$，并在读边时更新为相邻节点的最小 $a[][0]$，作为转移矩阵的参数。
• 离线 LCA：在 DFS 时，端点首次被访问即“激活”，相遇时 $findRoot$ 得到 LCA，挂到 LCA 延迟计算；避免在线 LCA 的复杂性。
• 矩阵乘使用“min-加”半环（不是普通加乘），注意是代价合并：$$res[i][j] = \min_k \big( a[i][k] + b[k][j] \big)$$
• 组合答案时要特别注意在 LCA 处的重复计数修正（$K=2/3$ 中的 $-a[LCA][0]$ 项）。
• IO 使用大缓冲读写，避免超时。

总结：
该解法将树上路径查询转化为“按状态的最优代价合并”问题。通过离线 LCA 与并查集路径压缩，在 DFS 过程中为每条查询构建从端点到 LCA 的状态转移，并用最小值加法的矩阵乘法累积段转移，最终以端点向量合并得到答案。根据 $K$ 的不同，状态维度与组合公式变化，但整体框架一致，时间性能稳定。

#include <bits/stdc++.h>
using namespace std;

// 类型定义：简化长整型书写
typedef long long i64;

// ===================== 快速IO模块（缓冲区优化，标准IO）=====================
const int BUFFER_SIZE = 1 << 20;  // 1MB缓冲区，减少IO次数
char readBuf[BUFFER_SIZE], *readPtr = readBuf, *readEnd = readBuf;
char writeBuf[BUFFER_SIZE], *writePtr = writeBuf;

// 从标准输入读取一个字符（缓冲区优化）
inline char readChar() {
    // 缓冲区空时，从标准输入（stdin）读取新数据填充
    if (readPtr == readEnd) {
        readEnd = readBuf + fread(readBuf, 1, BUFFER_SIZE, stdin);
        readPtr = readBuf;
    }
    return *readPtr++;
}

// 快速读取整数（支持负数，标准输入）
inline int readInt() {
    int val = 0;
    char ch = readChar();
    bool isNegative = false;

    // 跳过非数字、非负号的字符
    while (ch != '-' && (ch < '0' || ch > '9')) {
        ch = readChar();
    }

    // 处理负号
    if (ch == '-') {
        isNegative = true;
        ch = readChar();
    }

    // 读取数字部分
    while (ch >= '0' && ch <= '9') {
        val = val * 10 + (ch - '0');
        ch = readChar();
    }

    return isNegative ? -val : val;
}

// 刷新输出缓冲区到标准输出（控制台）
inline void flushWrite() {
    fwrite(writeBuf, 1, writePtr - writeBuf, stdout);
    writePtr = writeBuf;
}

// 写入一个字符到缓冲区（最终输出到控制台）
inline void writeChar(char c) {
    *writePtr++ = c;
    // 缓冲区满时刷新到标准输出
    if (writePtr == writeBuf + BUFFER_SIZE) {
        flushWrite();
    }
}

// 快速写入整数（支持负数，标准输出）
inline void writeInt(i64 val) {
    if (val == 0) {
        writeChar('0');
        return;
    }
    // 处理负数
    if (val < 0) {
        writeChar('-');
        val = -val;
    }

    // 数字转字符（先逆序存到数组，再反向输出）
    static char numBuf[32];
    int idx = 1;
    for (; val; idx++) {
        numBuf[idx] = val % 10 + '0';
        val /= 10;
    }

    // 反向输出数字
    for (idx--; idx >= 1; idx--) {
        writeChar(numBuf[idx]);
    }
}

// ===================== 全局常量与变量 =====================
const int MAX_NODE = 200000 + 5;  // 最大节点数
const i64 INF = 1e18;             // 表示无穷大（用于初始化最小代价）

int nodeCount;    // 节点总数（N）
int queryCount;   // 查询总数（Q）
int K;            // 场景类型（1/2/3，对应不同的代价计算规则）

// a[i][0]：节点i的基础权值（如传输成本）
// a[i][1]：节点i相邻节点的最小基础权值（预处理用）
i64 a[MAX_NODE][2];
i64 ans[MAX_NODE];  // 存储每个查询的结果

// 树的邻接表（双向边）
// edgeTo：边指向的节点；edgeNext：下一条边的索引；edgeLast：每个节点的最后一条边索引
int edgeTo[MAX_NODE << 1], edgeNext[MAX_NODE << 1], edgeLast[MAX_NODE];
// 查询的邻接表（双向存储，每个查询对应两条记录）
// queryTo：查询关联的节点；queryNext：下一个查询的索引；queryLast：每个节点的最后一个查询索引
int queryTo[MAX_NODE << 1], queryNext[MAX_NODE << 1], queryLast[MAX_NODE];

// 并查集相关（用于维护节点连通性，带路径压缩）
int parent[MAX_NODE];
// 状态转移矩阵（用于K=2/K=3场景，存储不同状态的最小代价）
i64 g[MAX_NODE][3][3];

// 待处理查询的链表（用于K=2/K=3，在LCA处集中处理查询）
int pendingLast[MAX_NODE];  // 每个节点的最后一个待处理查询
int pendingQueryId[MAX_NODE];// 待处理查询的ID
int pendingNext[MAX_NODE];  // 下一个待处理查询的索引
int pendingCount;           // 待处理查询的总数（P）

// 自定义三数最小值函数
inline i64 min3(i64 a, i64 b, i64 c) {
    a = (a > b) ? b : a;
    a = (a > c) ? c : a;
    return a;
}

// ===================== K=1 场景处理 =====================
namespace SceneK1 {
    // 并查集查找（带路径压缩）
    int findRoot(int x) {
        return (x == parent[x]) ? x : (parent[x] = findRoot(parent[x]));
    }

    // DFS遍历树，处理查询
    // u：当前节点；fa：当前节点的父节点
    void dfsSolve(int u, int fa) {
        parent[u] = u;  // 初始化并查集：自身为根
        // 计算当前节点的累计代价（从父节点继承）
        a[u][1] = a[fa][1] + a[u][0];

        // 处理当前节点关联的查询：若查询的另一节点已访问（有根），则计算结果
        for (int edgeIdx = queryLast[u]; edgeIdx; edgeIdx = queryNext[edgeIdx]) {
            int v = queryTo[edgeIdx];  // 查询的另一节点
            if (parent[v] != 0) {      // 若v已被访问（parent[v]已初始化）
                int lca = findRoot(v); // 找到u和v的最近公共祖先（LCA）
                // 计算查询结果：u到LCA的代价 + v到LCA的代价
                ans[edgeIdx >> 1] = a[v][1] + a[u][1] - 2 * a[lca][1] + a[lca][0];
            }
        }

        // 递归遍历子节点
        for (int edgeIdx = edgeLast[u]; edgeIdx; edgeIdx = edgeNext[edgeIdx]) {
            int v = edgeTo[edgeIdx];  // 子节点
            if (v != fa) {            // 避免回退到父节点
                dfsSolve(v, u);
                parent[v] = u;        // 合并并查集：子节点的根指向父节点
            }
        }
    }
}

// ===================== K=2 场景处理 =====================
namespace SceneK2 {
    // 向量与矩阵乘法（更新向量为“向量+矩阵”的最小代价）
    // a：输入输出向量（长度2）；b：输入矩阵（2x2）
    void multiplyVecMat(i64 a[3], const i64 b[][3]) {
        i64 res[2] = {INF, INF};
        // 计算res[j] = min(a[0]+b[0][j], a[1]+b[1][j])
#define CALC(j) res[j] = min(a[0] + b[0][j], a[1] + b[1][j]);
        CALC(0);
        CALC(1);
#undef CALC
        a[0] = res[0], a[1] = res[1];
    }

    // 矩阵与矩阵乘法（更新矩阵为“矩阵×矩阵”的最小代价）
    // a：输入输出矩阵（2x2）；b：输入矩阵（2x2）
    void multiplyMatMat(i64 a[][3], const i64 b[][3]) {
        i64 res[2][2] = {INF, INF, INF, INF};
        // 计算res[i][j] = min(a[i][0]+b[0][j], a[i][1]+b[1][j])
#define CALC(i, j) res[i][j] = min(a[i][0] + b[0][j], a[i][1] + b[1][j]);
        CALC(0, 0); CALC(0, 1);
        CALC(1, 0); CALC(1, 1);
#undef CALC
        // 结果回写
        a[0][0] = res[0][0], a[0][1] = res[0][1];
        a[1][0] = res[1][0], a[1][1] = res[1][1];
    }

    // 初始化子节点到父节点的状态转移矩阵
    // u：子节点；fa：父节点
    void initMatrix(int u, int fa) {
        // 矩阵g[u]表示从u到fa的状态转移代价
        g[u][0][0] = a[fa][0];  // 状态0→0的代价
        g[u][0][1] = 0;         // 状态0→1的代价
        g[u][1][0] = a[fa][0];  // 状态1→0的代价
        g[u][1][1] = INF;       // 状态1→1的代价（不可行）
    }

    // 并查集查找（带路径压缩+矩阵合并）
    int findRoot(int x) {
        if (x != parent[x]) {
            int origParent = parent[x];
            // 递归找到根节点（路径压缩）
            parent[x] = findRoot(origParent);
            // 若父节点已更新为根，合并状态矩阵（x到根的矩阵 = x到origParent的矩阵 × origParent到根的矩阵）
            if (parent[x] != origParent) {
                multiplyMatMat(g[x], g[origParent]);
            }
        }
        return parent[x];
    }

    // DFS遍历树，收集并处理查询
    void dfsSolve(int u, int fa) {
        parent[u] = u;  // 初始化并查集

        // 收集查询：若查询的另一节点已访问，将查询挂到LCA（根节点）的待处理列表
        for (int edgeIdx = queryLast[u]; edgeIdx; edgeIdx = queryNext[edgeIdx]) {
            int v = queryTo[edgeIdx];
            if (parent[v] != 0) {
                int lca = findRoot(v);  // 找到LCA
                // 新增待处理查询：记录查询ID、挂到LCA的待处理链表
                pendingCount++;
                pendingQueryId[pendingCount] = edgeIdx >> 1;
                pendingNext[pendingCount] = pendingLast[lca];
                pendingLast[lca] = pendingCount;
            }
        }

        // 递归遍历子节点
        for (int edgeIdx = edgeLast[u]; edgeIdx; edgeIdx = edgeNext[edgeIdx]) {
            int v = edgeTo[edgeIdx];
            if (v != fa) {
                dfsSolve(v, u);
                parent[v] = u;        // 合并并查集
                initMatrix(v, u);     // 初始化子节点v到父节点u的转移矩阵
            }
        }

        // 处理当前节点（LCA）的所有待处理查询
        i64 vecX[3], vecY[3];
        for (int pendingIdx = pendingLast[u]; pendingIdx; pendingIdx = pendingNext[pendingIdx]) {
            int qId = pendingQueryId[pendingIdx];  // 查询ID
            // 取出查询的两个节点（x和y）
            int x = queryTo[qId << 1 | 1];
            int y = queryTo[qId << 1];

            // 确保x和y的根都是当前LCA（u），并更新状态向量
            findRoot(x);
            findRoot(y);

            // 初始化x的状态向量：初始状态为“仅包含x自身”
            vecX[0] = a[x][0];
            vecX[1] = INF;
            if (x != u) {
                multiplyVecMat(vecX, g[x]);  // 合并x到LCA的状态矩阵
            }

            // 初始化y的状态向量：初始状态为“仅包含y自身”
            vecY[0] = a[y][0];
            vecY[1] = INF;
            if (y != u) {
                multiplyVecMat(vecY, g[y]);  // 合并y到LCA的状态矩阵
            }

            // 计算两种合法状态组合的最小代价
            ans[qId] = min(
                vecX[0] + vecY[0] - a[u][0],  // 状态0+0：减去LCA重复计算的代价
                vecX[1] + vecY[1]             // 状态1+1：无重复代价
            );
        }
    }
}

// ===================== K=3 场景处理 =====================
namespace SceneK3 {
    // 向量与矩阵乘法（3维：支持更多状态）
    void multiplyVecMat(i64 a[3], const i64 b[][3]) {
        i64 res[3] = {INF, INF, INF};
        // 计算res[j] = min(a[0]+b[0][j], a[1]+b[1][j], a[2]+b[2][j])
#define CALC(j) res[j] = min3(a[0] + b[0][j], a[1] + b[1][j], a[2] + b[2][j]);
        CALC(0);
        CALC(1);
        CALC(2);
#undef CALC
        a[0] = res[0], a[1] = res[1], a[2] = res[2];
    }

    // 矩阵与矩阵乘法（3x3：支持更多状态转移）
    void multiplyMatMat(i64 a[][3], const i64 b[][3]) {
        i64 res[3][3] = {
            {INF, INF, INF},
            {INF, INF, INF},
            {INF, INF, INF}
        };
        // 计算res[i][j] = min(a[i][0]+b[0][j], a[i][1]+b[1][j], a[i][2]+b[2][j])
#define CALC(i, j) res[i][j] = min3(a[i][0] + b[0][j], a[i][1] + b[1][j], a[i][2] + b[2][j]);
        CALC(0,0); CALC(0,1); CALC(0,2);
        CALC(1,0); CALC(1,1); CALC(1,2);
        CALC(2,0); CALC(2,1); CALC(2,2);
#undef CALC
        // 结果回写
        memcpy(a, res, sizeof(res));
    }

    // 初始化3维状态转移矩阵（支持K=3的多状态规则）
    void initMatrix(int u, int fa) {
        // g[u][i][j]：从u到fa的“状态i→状态j”的代价
        g[u][0][0] = a[fa][0];
        g[u][0][1] = 0;
        g[u][0][2] = INF;

        g[u][1][0] = a[fa][0];
        g[u][1][1] = a[fa][1];
        g[u][1][2] = 0;

        g[u][2][0] = a[fa][0];
        g[u][2][1] = INF;
        g[u][2][2] = INF;
    }

    // 并查集查找（带路径压缩+3维矩阵合并）
    int findRoot(int x) {
        if (x != parent[x]) {
            int origParent = parent[x];
            parent[x] = findRoot(origParent);
            if (parent[x] != origParent) {
                multiplyMatMat(g[x], g[origParent]);
            }
        }
        return parent[x];
    }

    // DFS遍历树，收集并处理查询（支持3维状态）
    void dfsSolve(int u, int fa) {
        parent[u] = u;

        // 收集待处理查询（逻辑同K=2）
        for (int edgeIdx = queryLast[u]; edgeIdx; edgeIdx = queryNext[edgeIdx]) {
            int v = queryTo[edgeIdx];
            if (parent[v] != 0) {
                int lca = findRoot(v);
                pendingCount++;
                pendingQueryId[pendingCount] = edgeIdx >> 1;
                pendingNext[pendingCount] = pendingLast[lca];
                pendingLast[lca] = pendingCount;
            }
        }

        // 递归处理子节点
        for (int edgeIdx = edgeLast[u]; edgeIdx; edgeIdx = edgeNext[edgeIdx]) {
            int v = edgeTo[edgeIdx];
            if (v != fa) {
                dfsSolve(v, u);
                parent[v] = u;
                initMatrix(v, u);
            }
        }

        // 处理当前LCA的待处理查询（3维状态组合）
        i64 vecX[3], vecY[3];
        for (int pendingIdx = pendingLast[u]; pendingIdx; pendingIdx = pendingNext[pendingIdx]) {
            int qId = pendingQueryId[pendingIdx];
            int x = queryTo[qId << 1 | 1];
            int y = queryTo[qId << 1];

            findRoot(x);
            findRoot(y);

            // 初始化x的状态向量
            vecX[0] = a[x][0];
            vecX[1] = vecX[2] = INF;
            if (x != u) multiplyVecMat(vecX, g[x]);

            // 初始化y的状态向量
            vecY[0] = a[y][0];
            vecY[1] = vecY[2] = INF;
            if (y != u) multiplyVecMat(vecY, g[y]);

            // 计算4种合法状态组合的最小代价
            ans[qId] = min3(
                vecX[0] + vecY[0] - a[u][0],  // 0+0
                vecX[1] + vecY[1],            // 1+1
                vecX[1] + vecY[2]             // 1+2
            );
            ans[qId] = min(ans[qId], vecX[2] + vecY[1]);  // 2+1
        }
    }
}

// ===================== 主函数（标准IO）=====================
int main() {
    // 关闭同步以配合自定义快速IO，提升效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 读取基本参数（标准输入）
    nodeCount = readInt();
    queryCount = readInt();
    K = readInt();

    // 初始化节点基础权值
    for (int i = 1; i <= nodeCount; i++) {
        a[i][0] = readInt();
        a[i][1] = INF;  // 初始化为无穷大，后续更新为相邻节点的最小权值
    }

    // 构建树的邻接表，并预处理每个节点的相邻最小权值
    int edgeIdx = 2;  // 边索引从2开始（成对存储，方便反向边）
    for (int i = 1; i < nodeCount; i++) {
        int x = readInt();
        int y = readInt();
        // 更新x和y的相邻最小权值
        a[x][1] = min(a[x][1], a[y][0]);
        a[y][1] = min(a[y][1], a[x][0]);
        // 存储双向边
        edgeTo[edgeIdx] = y;
        edgeNext[edgeIdx] = edgeLast[x];
        edgeLast[x] = edgeIdx++;

        edgeTo[edgeIdx] = x;
        edgeNext[edgeIdx] = edgeLast[y];
        edgeLast[y] = edgeIdx++;
    }

    // 构建查询的邻接表（双向存储）
    int queryIdx = 2;  // 查询索引从2开始（成对存储）
    for (int i = 1; i <= queryCount; i++) {
        int x = readInt();
        int y = readInt();
        // 存储x到y的查询关联
        queryTo[queryIdx] = y;
        queryNext[queryIdx] = queryLast[x];
        queryLast[x] = queryIdx++;

        // 存储y到x的查询关联
        queryTo[queryIdx] = x;
        queryNext[queryIdx] = queryLast[y];
        queryLast[y] = queryIdx++;
    }

    // 根据K值选择对应场景的求解逻辑
    memset(parent, 0, sizeof(parent));  // 初始化并查集为0（未访问）
    if (K == 1) {
        SceneK1::dfsSolve(1, 0);  // 以节点1为根开始DFS
    } else if (K == 2) {
        memset(pendingLast, 0, sizeof(pendingLast));  // 初始化待处理查询列表
        pendingCount = 0;
        SceneK2::dfsSolve(1, 0);
    } else {
        memset(pendingLast, 0, sizeof(pendingLast));  // 初始化待处理查询列表
        pendingCount = 0;
        SceneK3::dfsSolve(1, 0);
    }

    // 输出所有查询结果（标准输出到控制台）
    for (int i = 1; i <= queryCount; i++) {
        writeInt(ans[i]);
        writeChar('\n');
    }

    // 最后刷新缓冲区，确保所有输出都被打印
    flushWrite();
    return 0;
}