代码

#include <bits/stdc++.h>
using namespace std;
int dep[100005], father[100005], fa[100005][18], vet[200005], nxt[200005], head[200005], num,
    an2, ty, n, m, a, x, b, y, p[100005], u, v, logg[100005], now;
long long dp[100005][2], f[100005][18][2][2], oo = 3e10+5, ans;
char ch[5];
void add(int u, int v){
    num++;
    vet[num] = v;
    nxt[num] = head[u];
    head[u] = num;
}
int jump(int t, int k){
    for(int i = logg[k]; i >= 0; i--)
        if((1<<i)&k){
            t = father[fa[t][i]];
        }
    return  t;
}
void dfs(int u, int fat, int deep){
    dp[u][0] = 0; dp[u][1] = p[u];
    dep[u] = deep; father[u] = fat;
    fa[u][0] = u;
    for(int i = 1; i <= logg[dep[u]]; i++)
        fa[u][i] = fa[fa[father[u]][i-1]][i-1];
    for(int e = head[u]; e; e = nxt[e]){
        int v = vet[e];
        if(fat == v) continue;
        dfs(v, u, deep+1);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}
void dfsf(int i, int fat){
    for(int j = 1; j <= logg[dep[i]]; j++){
        int v = father[fa[i][j-1]];
        f[i][j][0][0] = min(f[i][j-1][0][1]+f[v][j-1][1][0],
                            f[i][j-1][0][0]+f[v][j-1][0][0]);
                       // + dp[father[fa[i][j]]][0] - dp[fa[i][j]][1];
        f[i][j][0][1] = min(f[i][j-1][0][1]+f[v][j-1][1][1],
                            f[i][j-1][0][0]+f[v][j-1][0][1]);
                       // + dp[father[fa[i][j]]][1] - min(dp[fa[i][j]][1], 
                       //                                 dp[fa[i][j]][0]) - p[father[fa[i][j]]];
        f[i][j][1][0] = min(f[i][j-1][1][1]+f[v][j-1][1][0],
                            f[i][j-1][1][0]+f[v][j-1][0][0]);
                      //  + dp[father[fa[i][j]]][0] - dp[fa[i][j]][1];
        f[i][j][1][1] = min(f[i][j-1][1][0]+f[v][j-1][0][1],
                            f[i][j-1][1][1]+f[v][j-1][1][1]);
                      //  + dp[father[fa[i][j]]][1] - min(dp[fa[i][j]][1], 
                      //                                  dp[fa[i][j]][0]) - p[father[fa[i][j]]];
    }
    for(int e = head[i]; e; e = nxt[e]){
        int v = vet[e];
        if(fat == v) continue;
        dfsf(v, i);
    }
}
int LCA(int a, int b){ //AC
    int delta = dep[b] - dep[a];
    an2 = b;
    b = jump(b, delta);
    //printf("(%d)", a);
    if (b == a) {
        an2 = jump(an2, dep[an2] - dep[a] - 1);
        return a;
    }
    for(int i = logg[dep[a]]; i >= 0; i--)
        if(father[fa[a][i]] != father[fa[b][i]]){
            a = father[fa[a][i]];
            b = father[fa[b][i]];
        }
    //printf("#%d#", an2);
    an2 = jump(an2, dep[an2] - dep[father[a]] - 1);
    return father[a];
}
long long solve(int first, int k, long long an, int y){
    if(k == 0) {
        if(ty == 1) return p[first] + min(dp[an2][0], dp[an2][1]);
        else return dp[an2][1];
    }
    //printf("(%d|%d|%d|%d)", first, k, an, y);
    int wei;
    if(an > ans) return oo;
    for(wei = logg[k]; wei >= 0; wei--)
        if(k&(1<<wei)) break;
    if(k == (1<<wei)) {
        an += f[first][wei][y][ty];
        ans = min(ans, an);
        //printf("#%lld#", f[first][wei][y][ty]);
        return an;
    }
    return min(solve(father[fa[first][wei]], k - (1<<wei), an + f[first][wei][y][0], 0),
               solve(father[fa[first][wei]], k - (1<<wei), an + f[first][wei][y][1], 1));
}
long long sl(int first, int k, long long an, int y){
    if(k == 0) return 0;
    ty = 0;
    //printf("a1");
    ans = oo; 
    long long  a1 = solve(first, k, an, y);
    ty = 1;
    //printf("a2");
    ans = oo;
    long long a2 = solve(first, k, an, y);
    return min(a1, a2);
}
int main(){
    for(int i = 1 ; i <= 100000 ; i++) ; for(int i = 1 ; i <= 100000 ; i++) ; 
    for(int i = 1 ; i <= 100000 ; i++) ; for(int i = 1 ; i <= 100000 ; i++) ;
    for(int i = 1 ; i <= 100000 ; i++) ; for(int i = 1 ; i <= 100000 ; i++) ;
    for(int i = 1 ; i <= 100000 ; i++) ; for(int i = 1 ; i <= 100000 ; i++) ;
    scanf("%d%d%s", &n, &m, ch);
    now = 0; 
    for(int i = 1; i <= n; i++){
        if(i <= 1<<now) logg[i] = now;
        else{
            now++;
            logg[i] = now;
        }
    }
    for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 0, 1);
    for(int i = 1; i <= n; i++){
        f[i][0][0][0] = oo;
        f[i][0][1][0] = dp[father[i]][0] - dp[i][1];
        f[i][0][0][1] = dp[father[i]][1] - min(dp[i][1], dp[i][0]);
        f[i][0][1][1] = f[i][0][0][1];
    }
    dfsf(1, 0);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d%d", &a, &x, &b, &y);
        if(dep[a] > dep[b]) {
            swap(a, b);
            swap(x, y);
        }
        int lca = LCA(a, b);
        //printf("%d|", lca);

        if(lca == a) {
            ty = x;
            ans = oo;
            long long anan = solve(b, dep[b] - dep[lca], 0, y) + dp[b][y] + sl(a, dep[a]-1, 0, x);
            if(anan >= oo) anan = -1;
            printf("%lld\n", anan);
            continue;
        }

        ty = 1;//lca点取
        ans = oo;
        long long kb = solve(b, dep[b] - dep[lca], 0, y);
        
        //printf("%d|", kb);
        kb = kb - dp[lca][1] + min(dp[an2][0], dp[an2][1]);//求出距离lca 1地方的值
       
        //printf("%d|", kb)
        ans = oo; 
        long long ka = solve(a, dep[a] - dep[lca], 0, x);
        long long anlca = ka - min(dp[an2][0], dp[an2][1]) + kb;
        long long lcan;
        ans = oo;
        if (dep[lca]!=1) lcan = sl(lca, dep[lca] - 1, 0, ty);
                         else lcan = 0;
        long long anan1;
        anan1 = lcan + anlca + dp[a][x] + dp[b][y];
        if(lca == a) anan1 -= dp[a][x];
        if(lca == a&&x == 0) anan1 = oo;
//--------------------------------------------------------------------------
        ty = 0;//lca点不取
        ans = oo;
        kb = solve(b, dep[b] - dep[lca], 0, y);
        //printf("%d|%d|", lca, an2);
        kb = kb - (dp[lca][0] - dp[an2][1]);//求出距离lca 1地方的值
        ans = oo;
        ka = solve(a, dep[a] - dep[lca], 0, x);
        anlca = ka - dp[an2][1] + kb;
        ans = oo;
        if (dep[lca]!=1) lcan = sl(lca, dep[lca] - 1, 0, ty);
                         else lcan = 0;
        //printf("%d|", anlca);
        long long anan2;
        anan2 = lcan + anlca + dp[a][x] + dp[b][y];
        if(lca == a) anan2 -= dp[a][x];

        long long anan = min(anan1, anan2);
        if(anan >= oo) anan = -1;
        printf("%lld\n", anan);
    }
    //printf("%lld|%lld|%lld|%lld", f[4][0][1][0], f[3][0][0][1], f[4][0][1][1], f[3][0][1][1]);
    return 0;
}

评测结果