代码

#include <cstdio>
#include <climits>

#define MAXN 300005
typedef long long ll;
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max(a, b) (((a) > (b)) ? (a) : (b))

inline ll read()
{
    char c = getchar();
    ll ret = 0;
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
    return ret;
}
void swap(int& a, int& b)
{
    int t = a;
    a = b, b = t;
}

const ll INF = (LLONG_MAX >> 2) - 1;
ll val[MAXN];

struct node
{
    int v, next;
}E[MAXN << 1];
int head[MAXN], Elen, N, M;
void add(int u, int v) { ++Elen, E[Elen].v = v, E[Elen].next = head[u], head[u] = Elen; }

int fa[MAXN][32], dep[MAXN];
ll dp[MAXN][3], g[MAXN][3], f[MAXN][32][3][3];

void dfs1(int u, int ff)
{
    int i, v;
    dep[u] = dep[ff] + 1, dp[u][1] = val[u], fa[u][0] = ff;
    for (i = 1; i <= 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (i = head[u]; i; i = E[i].next)
    {
        v = E[i].v;
        if (v == ff) continue;
        dfs1(E[i].v, u);
        dp[u][0] += dp[v][1], dp[u][1] += min(dp[v][0], dp[v][1]);
    }
    //printf("dp[%d][0/1]=%lld/%lld\n", u, dp[u][0], dp[u][1]);
}
void dfs2(int u, int ff)
{
    int v;
    for (int i = head[u]; i; i = E[i].next)
    {
        v = E[i].v;
        if (v == ff) continue;
        g[v][0] = g[u][1] + dp[u][1] - min(dp[v][0], dp[v][1]);
        g[v][1] = min(g[u][0] + dp[u][0] - dp[v][1], g[v][0]);
        dfs2(v, u);
    }
}
void dfs3(int u, int ff)
{
    int i, fff;
    f[u][0][0][0] = INF;
    f[u][0][0][1] = dp[fa[u][0]][1] - min(dp[u][0], dp[u][1]);
    f[u][0][1][0] = dp[fa[u][0]][0] - dp[u][1];
    f[u][0][1][1] = dp[fa[u][0]][1] - min(dp[u][0], dp[u][1]);
    for (i = 1; i <= 20; ++i)
    {
        fff = fa[u][i - 1];
        if (!fa[u][i])
        {
            //printf("(%d, %d)\n", u, i);
            f[u][i][0][0] = f[u][i][0][1] = f[u][i][1][0] = f[u][i][1][1] = INF;
            continue;
        }
        f[u][i][0][0] = min(f[u][i - 1][0][0] + f[fff][i - 1][0][0], f[u][i - 1][0][1] + f[fff][i - 1][1][0]);
        f[u][i][0][1] = min(f[u][i - 1][0][0] + f[fff][i - 1][0][1], f[u][i - 1][0][1] + f[fff][i - 1][1][1]);
        f[u][i][1][0] = min(f[u][i - 1][1][0] + f[fff][i - 1][0][0], f[u][i - 1][1][1] + f[fff][i - 1][1][0]);
        f[u][i][1][1] = min(f[u][i - 1][1][0] + f[fff][i - 1][0][1], f[u][i - 1][1][1] + f[fff][i - 1][1][1]);
    }
    for (i = head[u]; i; i = E[i].next) if (E[i].v != ff) dfs3(E[i].v, u);
}

ll solve(int u, int us, int v, int vs)
{
    if (dep[u] < dep[v]) swap(u, v), swap(us, vs);
    ll nowu[2] = {INF, INF}, lasu[2] = {INF, INF}, nowv[2] = {INF, INF}, lasv[2] = {INF, INF};
    int i, ff;
    lasu[us] = dp[u][us], lasv[vs] = dp[v][vs];
    for (i = 20; i >= 0; --i)
    {
        if (dep[fa[u][i]] < dep[v]) continue;
        nowu[0] = min(lasu[1] + f[u][i][1][0], lasu[0] + f[u][i][0][0]);
        nowu[1] = min(lasu[1] + f[u][i][1][1], lasu[0] + f[u][i][0][1]);
        lasu[0] = nowu[0], lasu[1] = nowu[1];
        u = fa[u][i];
    }
    //printf("%d %d %d %d %lld %lld %lld\n", u, us, v, vs, lasu[vs], g[u][vs], lasu[vs] + g[u][vs]);
    if (u == v) return lasu[vs] + g[u][vs];
    for (i = 20; i >= 0; --i)
    {
        if (fa[u][i] == fa[v][i]) continue;
        nowu[0] = min(lasu[1] + f[u][i][1][0], lasu[0] + f[u][i][0][0]);
        nowu[1] = min(lasu[1] + f[u][i][1][1], lasu[0] + f[u][i][0][1]);
        nowv[0] = min(lasv[1] + f[v][i][1][0], lasv[0] + f[v][i][0][0]);
        nowv[1] = min(lasv[1] + f[v][i][1][1], lasv[0] + f[v][i][0][1]);
        lasu[0] = nowu[0], lasu[1] = nowu[1], lasv[0] = nowv[0], lasv[1] = nowv[1];
        u = fa[u][i], v = fa[v][i];
    }
    ff = fa[u][0];
    ll ans0 = dp[ff][0] - dp[u][1] - dp[v][1] + lasu[1] + lasv[1] + g[ff][0];
    ll ans1 = dp[ff][1] - min(dp[u][0], dp[u][1]) - min(dp[v][0], dp[v][1]) + min(lasu[0], lasu[1]) + min(lasv[0], lasv[1]) + g[ff][1];
    return min(ans0, ans1);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    #endif
    N = read(), M = read(), read();
    int i, j, u, v, us, vs;
    for (i = 1; i <= N; ++i) val[i] = read();
    for (i = 1; i < N; ++i) u = read(), v = read(), add(u, v), add(v, u);
    dfs1(1, 0), dfs2(1, 0), dfs3(1, 0);
    /*for (i = 1; i <= N; ++i)
    {
        for (j = 0; j <= 3; ++j)
        {
            printf("f[%d][%d][0/1][0/1]=(00)%lld/(01)%lld/(10)%lld/(11)%lld\n", i, j, f[i][j][0][0], f[i][j][0][1], f[i][j][1][0], f[i][j][1][1]);
        }
    }
    for (i = 1; i <= N; ++i)
    {
        for (j = 0; j <= 3; ++j)
        {
            printf("fa[%d][%d]=%d\n", i, j, fa[i][j]);
        }
    }*/
    ll thisans;
    for (i = 1; i <= M; ++i)
    {
        u = read(), us = read(), v = read(), vs = read();
        thisans = solve(u, us, v, vs);
        //printf("ta=%lld\n", thisans);
        if (thisans >= INF) puts("-1");
        else printf("%lld\n", thisans);
    }
    return 0;
}

评测结果