CSP-S 2022 题解

A_box_of_yogurt · 2022-11-01 19:59:13 · 个人记录

补题终于补完辣！！1

有问题可以喷。

有不懂的可以问我。

T1 holiday

Meet in the middle。

可以理解为双向搜索。

注意到每条边是无向边，所以正着走和倒着走其实是一样的。

而且题目中景点的个数永远是4，\mathcal{O}(n^{4}) 的暴力肯定会超时，但是 \mathcal{O}(n^{2}) 却可以过，自然地想到 Meet in the middle。

具体地说，先枚举前两个景点（同时相当于枚举后两个点），设 dp_{i} 为表示第二个景点（或第三个）为点 i 的最大权值，同时需要记录次大值和次次大值以及选取的第一个景点（或第四个）。

接着枚举第二个和第三个景点，统计答案。注意这些点可能会重合，所以就是之前记录次大值和次次大值的作用，暴力枚举一下情况就行（相当于带上一个 9 的常数）。

挺简单的，但是考场上还是花了我100min。

丑陋的考场代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k, u, v, front, back, q[2500005][2], f[2505], mx[2505][3], e[2505][2505];
ll ans, s[2505], dp[2505][3];
vector<int> g[2505];
void dfs(const int& S, int now, int step) {
    if(now != S) {
        e[S][++e[S][0]] = now;
    }
    f[now] = step;
    ++step;
    if(step > k) return;
    const int LEN = g[now].size();
    for(int i = 0; i < LEN; ++i)
        if(step < f[g[now][i]]) dfs(S, g[now][i], step);
}
void calc(int A, int B, int C, int D) {
    if(mx[A][B] != mx[C][D] && mx[A][B] != C && mx[C][D] != A) ans = max(ans, dp[A][B] + dp[C][D]);
}
int main() {
    // freopen("holiday.in", "r", stdin);
    // freopen("holiday.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 2; i <= n; ++i) {
        scanf("%lld", &s[i]);
    }
    while(m--) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i) {
        dp[i][0] = dp[i][1] = dp[i][2] = -(1ll << 61);
        memset(f, 0x3f, sizeof(f));
        f[i] = -1;
        front = 0, back = -1;
        ++back, q[back][0] = i, q[back][1] = -1;
        while(front <= back) {
            u = q[front][0], v = q[front][1];
            ++front;
            if(v == f[u]) {
                if(u != i) {
                    e[i][++e[i][0]] = u;
                }
                if(f[u] + 1 > k) continue;
                const int LEN = g[u].size();
                for(int j = 0; j < LEN; ++j)
                    if(f[u] + 1 < f[g[u][j]]) {
                        ++back, q[back][0] = g[u][j], q[back][1] = f[u] + 1;
                        f[g[u][j]] = f[u] + 1;
                    }
                f[u] = -114514;
            }
        }
    }
    for(int i = 1; i <= e[1][0]; ++i) {
        u = e[1][i];
        for(int j = 1; j <= e[u][0]; ++j) {
            v = e[u][j];
            if(v != 1) {
                if(dp[v][0] < s[u] + s[v]) {
                    dp[v][2] = dp[v][1];
                    dp[v][1] = dp[v][0];
                    dp[v][0] = s[u] + s[v];
                    mx[v][2] = mx[v][1];
                    mx[v][1] = mx[v][0];
                    mx[v][0] = u;
                }
                else if(dp[v][1] < s[u] + s[v]) {
                    dp[v][2] = dp[v][1];
                    dp[v][1] = s[u] + s[v];
                    mx[v][1] = u;
                }
                else if(dp[v][2] < s[u] + s[v]) {
                    mx[v][2] = u;
                    dp[v][2] = s[u] + s[v];
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= e[i][0]; ++j) {
            v = e[i][j];
            calc(i, 0, v, 0);
            calc(i, 0, v, 1);
            calc(i, 0, v, 2);
            calc(i, 1, v, 0);
            calc(i, 1, v, 1);
            calc(i, 1, v, 2);
            calc(i, 2, v, 0);
            calc(i, 2, v, 1);
            calc(i, 2, v, 2);
        }
    }
    printf("%lld", ans);
    return 0;
}

T2 game

读完题后其实有一个很显然的思路，小L和小Q的决策肯定是在他们可选数字范围内的负数的最小值，负数的最大值，0，正数的最小值，正数的最大值中选取。（可以用一个很简单的贪心证明。）

小L先手，他要取最大值，小Q后手，他要取最小值。于是可以分类小L的每种情况，对应的答案就是能够达到的最小值，最终答案就是分类的最大值。（有点绕，可以仔细理解一下）。

（虽然但是，我考场还是打了一个分讨，常数会小一点，但是我不想讲了。）

于是打了8个st表。。

具体实现细节看代码吧（（（我太懒了

丑陋的考场代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int A = 0, B = 1, Z = 0, F = 1, MAX = 0, MIN = 1;
int n, m, q, l1, r1, l2, r2, a[100005], b[100005], lg[100005], sum[2][100005], st[2][2][2][100005][18];
bool z, f, flag[2][2][2][100005][18];
ll ans;
void read(int& x) {
    x = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f *= -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}
void write(ll x) {
    static char buffer[20];
    int p = -1;
    if(!x) {
        putchar('0');
        return;
    }
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    while(x) {
        buffer[++p] = (x % 10) ^ 48;
        x /= 10;
    }
    while(~p) putchar(buffer[p--]);
}
bool check(int AB, int ZF, int MAXMIN, int l, int r) {
    const int k = lg[r - l + 1];
    return (flag[AB][ZF][MAXMIN][l][k] || flag[AB][ZF][MAXMIN][r - (1 << k) + 1][k]);
}
ll ask(int AB, int ZF, int MAXMIN, int l, int r) {
    const int k = lg[r - l + 1];
    if(MAXMIN == MAX) {
        return max(st[AB][ZF][MAXMIN][l][k], st[AB][ZF][MAXMIN][r - (1 << k) + 1][k]);
    }
    else {
        return min(st[AB][ZF][MAXMIN][l][k], st[AB][ZF][MAXMIN][r - (1 << k) + 1][k]);
    }
}
int main() {
    // freopen("game.in", "r", stdin);
    // freopen("game.out", "w", stdout);
    read(n), read(m), read(q);
    memset(st[A][Z][MAX], 0x8f, sizeof(st[A][Z][MAX]));
    memset(st[A][F][MAX], 0x8f, sizeof(st[A][F][MAX]));
    memset(st[B][Z][MAX], 0x8f, sizeof(st[A][Z][MAX]));
    memset(st[B][F][MAX], 0x8f, sizeof(st[A][F][MAX]));
    memset(st[A][Z][MIN], 0x7f, sizeof(st[A][Z][MIN]));
    memset(st[A][F][MIN], 0x7f, sizeof(st[A][F][MIN]));
    memset(st[B][Z][MIN], 0x7f, sizeof(st[A][Z][MIN]));
    memset(st[B][F][MIN], 0x7f, sizeof(st[A][F][MIN]));
    for(int i = 2; i <= 100000; ++i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; ++i) {
        read(a[i]);
        sum[A][i] = sum[A][i - 1] + (a[i] == 0);
        if(a[i] > 0) {
            st[A][Z][MAX][i][0] = a[i];
            st[A][Z][MIN][i][0] = a[i];
            flag[A][Z][MAX][i][0] = true;
            flag[A][Z][MIN][i][0] = true;
        }
        if(a[i] < 0) {
            st[A][F][MAX][i][0] = a[i];
            st[A][F][MIN][i][0] = a[i];
            flag[A][F][MAX][i][0] = true;
            flag[A][F][MIN][i][0] = true;
        }
    }
    for(int i = 1; i <= m; ++i) {
        read(b[i]);
        sum[B][i] = sum[B][i - 1] + (b[i] == 0);
        if(b[i] > 0) {
            st[B][Z][MAX][i][0] = b[i];
            st[B][Z][MIN][i][0] = b[i];
            flag[B][Z][MAX][i][0] = true;
            flag[B][Z][MIN][i][0] = true;
        }
        if(b[i] < 0) {
            st[B][F][MAX][i][0] = b[i];
            st[B][F][MIN][i][0] = b[i];
            flag[B][F][MAX][i][0] = true;
            flag[B][F][MIN][i][0] = true;
        }
    }
    for(int i = 1; i <= lg[n]; ++i) {
        for(int j = 1; j <= n - (1 << i) + 1; ++j) {
            st[A][Z][MAX][j][i] = max(st[A][Z][MAX][j][i - 1], st[A][Z][MAX][j + (1 << (i - 1))][i - 1]);
            st[A][F][MAX][j][i] = max(st[A][F][MAX][j][i - 1], st[A][F][MAX][j + (1 << (i - 1))][i - 1]);
            st[A][Z][MIN][j][i] = min(st[A][Z][MIN][j][i - 1], st[A][Z][MIN][j + (1 << (i - 1))][i - 1]);
            st[A][F][MIN][j][i] = min(st[A][F][MIN][j][i - 1], st[A][F][MIN][j + (1 << (i - 1))][i - 1]);
            flag[A][Z][MAX][j][i] = flag[A][Z][MAX][j][i - 1] || flag[A][Z][MAX][j + (1 << (i - 1))][i - 1];
            flag[A][F][MAX][j][i] = flag[A][F][MAX][j][i - 1] || flag[A][F][MAX][j + (1 << (i - 1))][i - 1];
            flag[A][Z][MIN][j][i] = flag[A][Z][MIN][j][i - 1] || flag[A][Z][MIN][j + (1 << (i - 1))][i - 1];
            flag[A][F][MIN][j][i] = flag[A][F][MIN][j][i - 1] || flag[A][F][MIN][j + (1 << (i - 1))][i - 1];
        }
    }
    for(int i = 1; i <= lg[m]; ++i) {
        for(int j = 1; j <= m - (1 << i) + 1; ++j) {
            st[B][Z][MAX][j][i] = max(st[B][Z][MAX][j][i - 1], st[B][Z][MAX][j + (1 << (i - 1))][i - 1]);
            st[B][F][MAX][j][i] = max(st[B][F][MAX][j][i - 1], st[B][F][MAX][j + (1 << (i - 1))][i - 1]);
            st[B][Z][MIN][j][i] = min(st[B][Z][MIN][j][i - 1], st[B][Z][MIN][j + (1 << (i - 1))][i - 1]);
            st[B][F][MIN][j][i] = min(st[B][F][MIN][j][i - 1], st[B][F][MIN][j + (1 << (i - 1))][i - 1]);
            flag[B][Z][MAX][j][i] = flag[B][Z][MAX][j][i - 1] || flag[B][Z][MAX][j + (1 << (i - 1))][i - 1];
            flag[B][F][MAX][j][i] = flag[B][F][MAX][j][i - 1] || flag[B][F][MAX][j + (1 << (i - 1))][i - 1];
            flag[B][Z][MIN][j][i] = flag[B][Z][MIN][j][i - 1] || flag[B][Z][MIN][j + (1 << (i - 1))][i - 1];
            flag[B][F][MIN][j][i] = flag[B][F][MIN][j][i - 1] || flag[B][F][MIN][j + (1 << (i - 1))][i - 1];
        }
    }
    while(q--) {
        read(l1), read(r1), read(l2), read(r2);
        z = check(B, Z, MAX, l2, r2), f = check(B, F, MAX, l2, r2);
        if(z && f) {
            if(sum[A][r1] - sum[A][l1 - 1]) {
                puts("0");
            }
            else {
                ans = LONG_LONG_MIN;
                if(check(A, Z, MIN, l1, r1)) ans = ask(A, Z, MIN, l1, r1) * ask(B, F, MIN, l2, r2);
                if(check(A, F, MAX, l1, r1)) ans = max(ans, ask(A, F, MAX, l1, r1) * ask(B, Z, MAX, l2, r2));
                write(ans);
                putchar('\n');
            }
        }
        else if(z) {
            if(check(A, Z, MAX, l1, r1)) {
                if(sum[B][r2] - sum[B][l2 - 1]) {
                    puts("0");
                }
                else {
                    write(ask(A, Z, MAX, l1, r1) * ask(B, Z, MIN, l2, r2));
                    putchar('\n');
                }
            }
            else if(sum[A][r1] - sum[A][l1 - 1]) {
                puts("0");
            }
            else {
                write(ask(A, F, MAX, l1, r1) * ask(B, Z, MAX, l2, r2));
                putchar('\n');
            }
        }
        else if(f) {
            if(check(A, F, MIN, l1, r1)) {
                if(sum[B][r2] - sum[B][l2 - 1]) {
                    puts("0");
                }
                else {
                    write(ask(A, F, MIN, l1, r1) * ask(B, F, MAX, l2, r2));
                    putchar('\n');
                }
            }
            else if(sum[A][r1] - sum[A][l1 - 1]) {
                puts("0");
            }
            else {
                write(ask(A, Z, MIN, l1, r1) * ask(B, F, MIN, l2, r2));
                putchar('\n');
            }
        }
        else {
            puts("0");
        }
    }
    return 0;
}

T3 galaxy

首先发现这道题的判断答案的第一个要求是没有用的，因为如果每一个点都有出度（也就是每一个点都有一条出边），那么到达任意一个点都可以走下去，也就是无限地走下去了。

很容易想到维护每条有向边的起点所构成的点集，但是如何高效？

如果能把一个点集转化为一个值，那么比较的复杂度就会从 \mathcal{O}(m) 将为 \mathcal{O}(1)，想到了什么？哈希！

我们定义编号为 i 的点的哈希值为 114514 ^ {i} \bmod 19260817（后文将取模的步骤省略），显然可以进行反击的哈希值就是 \sum\limits_{i = 1} ^ {n} {114514 ^ {i}}。

我们可以先统计出来当前的图的哈希值（假设为 now），输入时将每个结点为一条边的终点对应的起点的哈希和统计出来（假设为 f_{i}），再统计每个结点为终点对应的已经被删除的起点的哈希和（假设为 c_{i}）。

每次操作完比较一下 now 和 \sum\limits_{i = 1} ^ {n} {114514 ^ {i}} 即可。

丑陋的补题代码：

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
namespace VividCycle {
    #include <bits/stdc++.h>
    #define getchar gc
    #define putchar pc
    #define fu(i, l, r) for(int i = l; i <= r; ++i)
    #define fd(i, l, r) for(int i = l; i >= r; --i)
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    static char buffer[1 << 20 | 1]; static int outp = -1;
    void flush() {fwrite(buffer, 1, outp + 1, stdout), outp = -1;}
    void pc(const char& ch) {if(outp == (1 << 20)) flush(); buffer[++outp] = ch;}
    char gc() {static char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf; return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1000010, stdin), p1 == p2) ? -1 : *p1++;}
    template<typename T> void read(T& x) {x = 0; int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') f *= ((ch == '-') ? -1 : 1), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f;}
    template<typename T, typename ...Args> void read(T& x, Args& ...args) {read(x), read(args...);}
    void write(const char& ch) {putchar(ch);} void write(const char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);} void write(char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);}
    template<typename T> void write(T x) {static char obuf[1 << 8]; static int p; p = 0; if(x < 0) x *= (putchar('-'), -1); if(!x) {putchar('0'); return;} while(x) obuf[++p] = x % 10 ^ 48, x /= 10; while(p) putchar(obuf[p--]);}
    template<typename T, typename ...Args> void write(T x, Args ...args) {write(x), write(args...);}
}
using namespace VividCycle;
const int mod = 19260817;
int n, m, q, t, u, v, ans, now, f[500001], c[500001], base[500001];
int main() {
    read(n, m);
    base[0] = 1;
    fu(i, 1, n) base[i] = base[i - 1] * 114514ll % mod, ans = (ans + base[i]) % mod;
    while(m--) {
        read(u, v);
        f[v] = (f[v] + base[u]) % mod;
        now = (now + base[u]) % mod;
    }
    read(q);
    while(q--) {
        read(t);
        if(t & 1) {
            read(u, v);
            if(t == 1) {
                now = ((now - base[u]) % mod + mod) % mod;
                c[v] = (c[v] + base[u]) % mod;
            }
            else {
                now = (now + base[u]) % mod;
                c[v] = ((c[v] - base[u]) % mod + mod) % mod;
            }
        }
        else {
            read(u);
            if(t == 2) {
                now = ((now - f[u] + c[u]) % mod + mod) % mod;
                c[u] = f[u];
            }
            else {
                now = (now + c[u]) % mod;
                c[u] = 0;
            }
        }
        write(now == ans ? "YES\n" : "NO\n");
    }
    flush();
    return 0;
}

咕咕咕，晚上晚自习再补。

先把T4代码放上吧：

T4:

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
namespace VividCycle {
    #include <bits/stdc++.h>
    #define getchar gc
    #define putchar pc
    #define fu(i, l, r) for(int i = l; i <= r; ++i)
    #define fd(i, l, r) for(int i = l; i >= r; --i)
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    static char buffer[1 << 20 | 1]; static int outp = -1;
    void flush() {fwrite(buffer, 1, outp + 1, stdout), outp = -1;}
    void pc(const char& ch) {if(outp == (1 << 20)) flush(); buffer[++outp] = ch;}
    char gc() {static char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf; return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1000010, stdin), p1 == p2) ? -1 : *p1++;}
    template<typename T> void read(T& x) {x = 0; int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') f *= ((ch == '-') ? -1 : 1), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f;}
    template<typename T, typename ...Args> void read(T& x, Args& ...args) {read(x), read(args...);}
    void write(const char& ch) {putchar(ch);} void write(const char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);} void write(char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);}
    template<typename T> void write(T x) {static char obuf[1 << 8]; static int p; p = 0; if(x < 0) x *= (putchar('-'), -1); if(!x) {putchar('0'); return;} while(x) obuf[++p] = x % 10 ^ 48, x /= 10; while(p) putchar(obuf[p--]);}
    template<typename T, typename ...Args> void write(T x, Args ...args) {write(x), write(args...);}
}
using namespace VividCycle;
const ll inf = 1ll << 60;
ll n, q, k, a, b, lg[200001], v[200001], dep[200001], fa[200001][19];
vector<int> g[200001];
void dfs(int now, int father) {
    dep[now] = dep[father] + 1;
    fa[now][0] = father;
    fu(i, 1, lg[n]) fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for(const auto& i : g[now]) {
        if(i != father) dfs(i, now);
    }
}
int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]]];
    if(x == y) return x;
    fd(i, lg[n], 0) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
namespace Solution1 {
    ll sum[200001];
    void dfs(int now, int father) {
        sum[now] = sum[father] + v[now];
        for(const auto& i : g[now]) {
            if(i != father) dfs(i, now);
        }
    }
    void init() {
        dfs(1, 0);
    }
    ll solve(int s, int t) {
        int LCA = lca(s, t);
        return sum[s] + sum[t] - sum[LCA] - sum[fa[LCA][0]];
    }
}
namespace Solution2 {
    struct matrix {
        ll v[2][2];
        matrix(ll V = inf) {v[0][0] = v[1][1] = V; v[0][1] = v[1][0] = inf;}
        matrix operator * (const matrix& b) const {
            matrix ret;
            fu(i, 0, 1) {
                fu(j, 0, 1) {
                    fu(k, 0, 1) {
                        ret.v[i][k] = min(ret.v[i][k], v[i][j] + b.v[j][k]);
                    }
                }
            }
            return ret;
        }
    };
    matrix up[200001][19], down[200001][19];
    matrix get_matrix(int x) {
        matrix ret;
        ret.v[0][0] = ret.v[1][0] = v[x];
        ret.v[0][1] = 0;
        return ret;
    }
    void init() {
        fu(i, 1, n) {
            up[i][0] = down[i][0] = get_matrix(i);
        }
        fu(i, 1, lg[n]) {
            fu(j, 1, n) {
                up[j][i] = up[j][i - 1] * up[fa[j][i - 1]][i - 1];
                down[j][i] = down[fa[j][i - 1]][i - 1] * down[j][i - 1];
            }
        }
    }
    matrix get_up(int x, int y) {
        matrix ret(0);
        while(dep[x] > dep[y]) ret = ret * up[x][lg[dep[x] - dep[y]]], x = fa[x][lg[dep[x] - dep[y]]];
        return ret;
    }
    matrix get_down(int x, int y) {
        matrix ret(0);
        while(dep[x] > dep[y]) ret = down[x][lg[dep[x] - dep[y]]] * ret, x = fa[x][lg[dep[x] - dep[y]]];
        return ret;
    }
    ll solve(int s, int t) {
        int LCA = lca(s, t);
        matrix ans = get_up(s, LCA) * get_matrix(LCA) * get_down(t, LCA);
        return min(ans.v[1][0], ans.v[1][1] + v[t]);
    }
}
namespace Solution3 {
    struct matrix {
        ll v[3][3];
        matrix(ll V = inf) {v[0][0] = v[1][1] = v[2][2] = V; v[0][1] = v[0][2] = v[1][0] = v[1][2] = v[2][0] = v[2][1] = inf;}
        matrix operator * (const matrix& b) const {
            matrix ret;
            fu(i, 0, 2) {
                fu(j, 0, 2) {
                    fu(k, 0, 2) {
                        ret.v[i][k] = min(ret.v[i][k], v[i][j] + b.v[j][k]);
                    }
                }
            }
            return ret;
        }
    };
    matrix up[200001][19], down[200001][19];
    ll min_son[200001];
    void dfs(int now, int father) {
        min_son[now] = inf;
        for(const auto& i : g[now]) {
            if(i != father) {
                dfs(i, now);
                min_son[now] = min(min_son[now], v[i]);
            }
        }
    }
    matrix get_matrix(int x, ll V = inf) {
        matrix ret;
        ret.v[0][0] = ret.v[1][0] = ret.v[2][0] = v[x];
        ret.v[0][1] = 0, ret.v[1][1] = min(min_son[x], V);
        ret.v[1][2] = 0;
        return ret;
    }
    void init() {
        dfs(1, 0);
        fu(i, 1, n) {
            up[i][0] = down[i][0] = get_matrix(i);
        }
        fu(i, 1, lg[n]) {
            fu(j, 1, n) {
                up[j][i] = up[j][i - 1] * up[fa[j][i - 1]][i - 1];
                down[j][i] = down[fa[j][i - 1]][i - 1] * down[j][i - 1];
            }
        }
    }
    matrix get_up(int x, int y) {
        matrix ret(0);
        while(dep[x] > dep[y]) ret = ret * up[x][lg[dep[x] - dep[y]]], x = fa[x][lg[dep[x] - dep[y]]];
        return ret;
    }
    matrix get_down(int x, int y) {
        matrix ret(0);
        while(dep[x] > dep[y]) ret = down[x][lg[dep[x] - dep[y]]] * ret, x = fa[x][lg[dep[x] - dep[y]]];
        return ret;
    }
    ll solve(int s, int t) {
        int LCA = lca(s, t);
        matrix ans = get_up(s, LCA) * get_matrix(LCA, v[fa[LCA][0]]) * get_down(t, LCA);
        return min(ans.v[2][0], min(ans.v[2][1], ans.v[2][2]) + v[t]);
    }
}
int main() {
    read(n, q, k);
    v[0] = inf;
    fu(i, 1, n) read(v[i]);
    fu(i, 2, n) {
        read(a, b);
        g[a].push_back(b);
        g[b].push_back(a);
        lg[i] = lg[i >> 1] + 1;
    }
    dfs(1, 0);
    switch(k) {
        case 1: Solution1::init(); break;
        case 2: Solution2::init(); break;
        case 3: Solution3::init(); break;
    }
    while(q--) {
        read(a, b);
        switch(k) {
            case 1: write(Solution1::solve(a, b), '\n'); break;
            case 2: write(Solution2::solve(a, b), '\n'); break;
            case 3: write(Solution3::solve(a, b), '\n'); break;
        }
    }
    flush();
    return 0;
}