代码

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f, N = 100010;

int n, m, xx, yy, aa, bb, lca;
LL val[N], f0[N], f1[N], nf0[N], nf1[N], vis[N], 
    fa[N], dep[N], g0[N], g1[N], path[N];
char type[5];
vector<int> e[N];
queue<int> q;

LL init_dfs(int u, int father){
    for(int i = 0; i < e[u].size(); i++){
        int v = e[u][i];
        if(v == father){ fa[u] = v; continue; }
        f1[u] += init_dfs(v, u);
        f0[u] += f1[v];
    }
    f1[u] += val[u];
    return min(f0[u], f1[u]);
}

void bfs(){
    dep[1] = 1;
    nf1[1] = val[1];
    q.push(1); vis[1] = 1;
    while(q.size()){
        int u = q.front(); q.pop();
        for(int i = 0; i < e[u].size(); i++){
            int v = e[u][i];
            if(vis[v]) continue;
            nf0[v] = nf1[u] + f1[u] - val[u] - min(f0[v], f1[v]);
            nf1[v] = min(nf1[u] + f1[u]- val[u] - min(f0[v], f1[v]), 
                     	 nf0[u] + f0[u] - f1[v]) + val[v];
            q.push(v); vis[v] = 1; dep[v] = dep[u] + 1;
        }
    }
    return;
}

int find_lca(int a, int b){
    int x = a, y = b;
    path[x] = 1, path[y] = 1;
    if(dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) x = fa[x], path[x] = 1;
    while(x != y) x = fa[x], y = fa[y], path[x] = 1, path[y] = 1;
    return x;
}

int dfs(int u){
    if(!path[u]){
        g0[u] = f0[u], g1[u] = f1[u];
        return min(g0[u], g1[u]);
    } 
    if(u == aa && u != lca){
        if(xx) return g1[u] = f1[u];
        else { g1[u] = INF; return g0[u] = f0[u]; }
    } 
    if(u == bb && u != lca){
        if(yy) return g1[u] = f1[u];
        else { g1[u] = INF; return g0[u] = f0[u]; }
    }
    for(int i = 0; i < e[u].size(); i++){
        int v = e[u][i];
        if(v == fa[u]) continue;
        g1[u] += dfs(v);
        g0[u] += g1[v];
    }
    g1[u] += val[u];
    return min(g0[u], g1[u]);
}

int main(){
    cin >> n >> m;
    cin >> type;
    for(int i = 1; i <= n; i++) cin >> val[i];
    for(int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        e[x].push_back(y), e[y].push_back(x);
    }
    init_dfs(1, 0);
    bfs();
    for(int i = 1; i <= m; i++){
    	memset(g0, 0, sizeof(g0));
    	memset(g1, 0, sizeof(g1));
    	memset(path, 0, sizeof(path));
        cin >> aa >> xx >> bb >> yy;
        lca = find_lca(aa, bb);
        dfs(lca);
        if((lca == aa && !xx) || (lca == bb && !yy)) g1[lca] = INF;
        if((lca == aa && xx) || (lca == bb && yy)) g0[lca] = INF;
        int ans = min(nf0[lca] + g0[lca], nf1[lca] + g1[lca] - val[lca]);
        if(ans >= INF) cout << -1 << endl;
        else cout << ans << endl;
    }
    return 0;
}

评测结果