代码

#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cstdlib>

#include <algorithm>
#include <numeric>
#include <limits>
#include <functional>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <queue>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

struct Edge {
    int v;
    Edge *next;
};

ll ad(ll x, ll y) {
    if (~x & ~y)
        return x + y;
    return -1;
}

bool cmp(ll x, ll y) {
    return x != -1 && (x < y || y == -1);
}

struct Mat {
    ll gr[2][2];

    Mat() { memset(gr, -1, sizeof(gr)); }

    Mat(const Mat& rhs) { memcpy(gr, rhs.gr, sizeof(gr)); }

    ll* operator[](int k) { return gr[k]; }
    const ll* operator[](int k) const { return gr[k]; }

    void dbg() const {
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                LOG("%lld ", gr[i][j]);
            }
            LOG("\n");
        }
    }

    Mat operator*(const Mat& rhs) const {
        Mat m = Mat();
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k)
                    m[i][j] = min(m[i][j], ad(gr[i][k], rhs.gr[k][j]), cmp);
            }
//		dbg();
//		rhs.dbg();
//		m.dbg();
        return m;
    }
};

const int N = 100010;

int n, m;
char s[5];
bool vis[N];
int p[N], f[N], qa[N], qx[N], qb[N], qy[N], lca[N];
Mat dt[N];
ll ans[N];
ll dp[N][2], tmp[N][2];
Edge* g[N];
vector<pair<int, int> > ql[N];
vector<int> qr[N];

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

int find2(int x) {
    if (f[x] == x)
        return x;
    int prt = f[x];
    f[x] = find2(prt);
    dt[x] = dt[prt] * dt[x];
    return f[x];
}

void adde(int u, int v);
void tarjan(int u);
void dfs(int u);

int main() {
    scanf("%d%d%s", &n, &m, s);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &p[i]);
    for (int rep = 1; rep < n; ++rep) {
        int u, v;
        scanf("%d%d", &u, &v);
        adde(u, v);
        adde(v, u);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d", &qa[i], &qx[i], &qb[i], &qy[i]);
        ql[qa[i]].push_back(make_pair(qb[i], i));
        ql[qb[i]].push_back(make_pair(qa[i], i));
    }
    tarjan(1);
    for (int i = 1; i <= m; ++i)
        qr[lca[i]].push_back(i);
    memset(vis, 0, sizeof(vis));
    memset(f, 0, sizeof(f));
    {
        Mat model = Mat();
        model[0][0] = model[1][1] = 0;
        fill(dt + 1, dt + n + 1, model);
    }
    dfs(1);
    for (int i = 1; i <= m; ++i) {
        int lc = lca[i];
        find2(lc);
        ans[i] = -1;
//		LOG("%d: %lld %lld\n", i, tmp[i][0], tmp[i][1]);;
        for (int k = 0; k < 2; ++k)
            for (int j = 0; j < 2; ++j)
                ans[i] = min(ans[i], ad(dt[lc][k][j], tmp[i][j]), cmp);
        printf("%lld\n", ans[i]);
    }
    return 0;
}

void dfs(int u) {
    vis[u] = true;
    f[u] = u;
    dp[u][1] = p[u];
    for (Edge* p = g[u]; p; p = p->next)
        if (!vis[p->v]) {
            dfs(p->v);
            dp[u][0] += dp[p->v][1];
            dp[u][1] += min(dp[p->v][0], dp[p->v][1]);
        }
    for (int i = 0; i < qr[u].size(); ++i) {
        int id = qr[u][i];
        int &a = qa[id], &x = qx[id], &b = qb[id], &y = qy[id];
        if (u == b) {
            swap(a, b);
            swap(x, y);
        }
        if (u != a) {
            find2(a);
            find2(b);
            for (int k = 0; k < 2; ++k) {
                tmp[id][k] = -1;
                ll sub = dp[u][k];
                if (k == 0)
                    sub -= dp[f[a]][1] + dp[f[b]][1];
                else
                    sub -= min(dp[f[a]][0], dp[f[a]][1]) + min(dp[f[b]][0], dp[f[b]][1]);

                if (k == 0)
                    tmp[id][0] = ad(dp[a][x] + dp[b][y], ad(sub, ad(dt[a][1][x], dt[b][1][y])));
                else
                    tmp[id][1] = ad(dp[a][x] + dp[b][y] + sub, ad(min(dt[a][1][x], dt[a][0][x], cmp), min(dt[b][1][y], dt[b][0][y], cmp)));
            }
        }
    }
    for (Edge* p = g[u]; p; p = p->next)
        if (!vis[p->v]) {
            f[p->v] = u;
            dt[p->v][0][0] = -1;
            dt[p->v][0][1] = dp[u][0] - dp[p->v][1];
            dt[p->v][1][0] = dt[p->v][1][1] = dp[u][1] - min(dp[p->v][0], dp[p->v][1]);
        }
    for (int i = 0; i < qr[u].size(); ++i) {
        int id = qr[u][i];
        int a = qa[id], x = qx[id], b = qb[id], y = qy[id];
        if (u == a) {
            find2(b);
//			LOG("%d(from %d)%d %d\n", f[b], b, f[f[b]], u);
            tmp[id][x] = ad(dt[b][x][y], dp[b][y]);
//			LOG("%lld\n", dt[b][x][y]);
            tmp[id][!x] = -1;
        }
    }
    vis[u] = false;
}

void tarjan(int u) {
    static bool vis[N];
    vis[u] = true;
    f[u] = u;
    for (Edge* p = g[u]; p; p = p->next)
        if (!vis[p->v]) {
            tarjan(p->v);
            f[p->v] = u;
        }
    for (int i = 0; i < ql[u].size(); ++i)
        if (f[ql[u][i].first])
            lca[ql[u][i].second] = find(ql[u][i].first);
}

void adde(int u, int v) {
    static Edge pool[N * 2];
    static Edge* p = pool;
    p->v = v;
    p->next = g[u];
    g[u] = p;
    ++p;
}

评测结果