代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define maxn 100001
using namespace std;
const long long inf=1e18;
int n,m,val[maxn];
char shape[5];
inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
/***********************************************************/
struct edge{
    int to,next;
    edge(){}
    edge(const int &_to,const int &_next){ to=_to,next=_next; }
}e[maxn<<1];
int head[maxn],k;
inline void add(const int &u,const int &v){ e[k]=edge(v,head[u]),head[u]=k++; }
/*****************************************************************************/
namespace pts55{
    long long dp[maxn][2];
    void dfs(int u,int pre){
        for(register int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(v==pre) continue;
            dfs(v,u);
            dp[u][0]+=dp[v][1],dp[u][1]+=min(dp[v][0],dp[v][1]);
        }
    }
    inline void solve(){
        for(register int i=1;i<=m;i++){
            for(register int i=1;i<=n;i++) dp[i][0]=0,dp[i][1]=val[i];
            int u=read(),op1=read(),v=read(),op2=read();
            dp[u][op1^1]=dp[v][op2^1]=inf;
            dfs(1,-1);
            printf("%lld\n",min(dp[1][0],dp[1][1])>=inf?-1:min(dp[1][0],dp[1][1]));
        }
    }
}
/*********************************************************************************/
namespace pts65{
    long long dp[maxn][2],dp2[maxn][2],ndp[maxn][2];
    int fa[maxn],dep[maxn];
    void dfs(int u,int pre){
        dp[u][0]=0,dp[u][1]=val[u];
        for(register int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(v==pre) continue;
            fa[v]=u,dep[v]=dep[u]+1,dfs(v,u);
            dp[u][0]+=dp[v][1],dp[u][1]+=min(dp[v][0],dp[v][1]);
        }
    }
    void dfs2(int u,int pre){
        for(register int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(v==pre) continue;
            ndp[v][1]=min(ndp[u][0]+dp[u][0]-dp[v][1],ndp[u][1]+dp[u][1]-min(dp[v][0],dp[v][1]));
            ndp[v][0]=ndp[u][1]+dp[u][1]-min(dp[v][0],dp[v][1]);
            dfs2(v,u);
        }
    }
    inline long long getans(int u,int v){
        if(dep[u]>dep[v]) swap(u,v);
        while(dep[v]>dep[u]&&fa[v]!=u){
            dp2[fa[v]][1]=dp[fa[v]][1]-min(dp[v][1],dp[v][0])+min(dp2[v][1],dp2[v][0]);
            dp2[fa[v]][0]=dp[fa[v]][0]-dp[v][1]+dp2[v][1];
            v=fa[v];
        }
        if(fa[v]==u){
            dp2[fa[v]][1]=dp2[fa[v]][1]-min(dp[v][1],dp[v][0])+min(dp2[v][1],dp2[v][0]);
            dp2[fa[v]][0]=dp2[fa[v]][0]-dp[v][1]+dp2[v][1];
            v=fa[v];
        }
        while(fa[u]!=fa[v]){
            dp2[fa[u]][1]=dp[fa[u]][1]-min(dp[u][1],dp[u][0])+min(dp2[u][1],dp2[u][0]);
            dp2[fa[u]][0]=dp[fa[u]][0]-dp[u][1]+dp2[u][1];
            dp2[fa[v]][1]=dp[fa[v]][1]-min(dp[v][1],dp[v][0])+min(dp2[v][1],dp2[v][0]);
            dp2[fa[v]][0]=dp[fa[v]][0]-dp[v][1]+dp2[v][1];
            u=fa[u],v=fa[v];
        }
        if(u!=v){
            dp2[fa[u]][1]=dp[fa[u]][1]-min(dp[u][1],dp[u][0])+min(dp2[u][1],dp2[u][0])-min(dp[v][1],dp[v][0])+min(dp2[v][1],dp2[v][0]);
            dp2[fa[u]][0]=dp[fa[u]][0]-dp[u][1]+dp2[u][1]-dp[v][1]+dp2[v][1];
            u=fa[u];
        }
        return min(dp2[u][1]+ndp[u][1],dp2[u][0]+ndp[u][0]);
    }
    inline void solve(){
        dfs(1,-1),dfs2(1,-1);
        for(register int i=1;i<=m;i++){
            int u=read(),op1=read(),v=read(),op2=read();
            dp2[u][op1]=dp[u][op1],dp2[u][!op1]=inf;
            dp2[v][op2]=dp[v][op2],dp2[v][!op2]=inf;
            long long ans=getans(u,v);
            printf("%lld\n",ans>=inf?-1:ans);
        }
    }
}
/*************************************************************************************************************************************/
namespace pts100{
    long long dp[maxn][2],ndp[maxn][2],dp2[maxn][20][2][2];
    int dep[maxn],fa[maxn][20],maxdep;
    void dfs(int u,int pre){
        dp[u][0]=0,dp[u][1]=val[u];
        for(register int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(v==pre) continue;
            dep[v]=dep[u]+1,fa[v][0]=u,dfs(v,u);
            dp[u][0]+=dp[v][1],dp[u][1]+=min(dp[v][0],dp[v][1]);
        }
    }
    void dfs2(int u,int pre){
        for(register int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(v==pre) continue;
            ndp[v][1]=min(ndp[u][0]+dp[u][0]-dp[v][1],ndp[u][1]+dp[u][1]-min(dp[v][0],dp[v][1]));
            ndp[v][0]=ndp[u][1]+dp[u][1]-min(dp[v][0],dp[v][1]);
            dfs2(v,u);
        }
    }
    inline void prework(){
        maxdep=(int)log(n)/log(2)+1;
        for(register int i=1;i<=n;i++){
            dp2[i][0][0][0]=inf;
            dp2[i][0][0][1]=dp[fa[i][0]][1]-min(dp[i][0],dp[i][1]);
            dp2[i][0][1][0]=dp[fa[i][0]][0]-dp[i][1];
            dp2[i][0][1][1]=dp[fa[i][0]][1]-min(dp[i][0],dp[i][1]);
        }
        for(register int j=1;j<=maxdep;j++){
            for(register int i=1;i<=n;i++){
                fa[i][j]=fa[fa[i][j-1]][j-1];
                for(register int p=0;p<=1;p++){
                    for(register int q=0;q<=1;q++){
                        dp2[i][j][p][q]=min(dp2[i][j-1][p][0]+dp2[fa[i][j-1]][j-1][0][q],dp2[i][j-1][p][1]+dp2[fa[i][j-1]][j-1][1][q]);
                    }
                }
            }
        }
    }
    inline long long getans(int u,int op1,int v,int op2){
        if(dep[u]>dep[v]) swap(u,v),swap(op1,op2);
        long long sum_u[2],ans_u[2],sum_v[2],ans_v[2];
        ans_u[op1]=dp[u][op1],ans_v[op2]=dp[v][op2];
        ans_u[!op1]=ans_v[!op2]=inf;
        for(register int i=maxdep;i>=0;i--) if(dep[fa[v][i]]>=dep[u]){
            sum_v[0]=sum_v[1]=inf;
            for(register int p=0;p<=1;p++){
                for(register int q=0;q<=1;q++){
                    sum_v[q]=min(sum_v[q],dp2[v][i][p][q]+ans_v[p]);
                }
            }
            ans_v[0]=sum_v[0],ans_v[1]=sum_v[1],v=fa[v][i];
        }
        if(u==v) return ans_v[op1]+ndp[u][op1];
        for(register int i=maxdep;i>=0;i--) if(fa[u][i]!=fa[v][i]){
            sum_u[0]=sum_u[1]=sum_v[0]=sum_v[1]=inf;
            for(register int p=0;p<=1;p++){
                for(register int q=0;q<=1;q++){
                    sum_u[q]=min(sum_u[q],dp2[u][i][p][q]+ans_u[p]);
                    sum_v[q]=min(sum_v[q],dp2[v][i][p][q]+ans_v[p]);
                }
            }
            ans_u[0]=sum_u[0],ans_u[1]=sum_u[1],u=fa[u][i];
            ans_v[0]=sum_v[0],ans_v[1]=sum_v[1],v=fa[v][i];
        }
        int f=fa[u][0];
        return min(dp[f][0]-dp[u][1]+ans_u[1]-dp[v][1]+ans_v[1]+ndp[f][0],dp[f][1]-min(dp[u][0],dp[u][1])+min(ans_u[0],ans_u[1])-min(dp[v][0],dp[v][1])+min(ans_v[0],ans_v[1])+ndp[f][1]);
    }
    inline void solve(){
        dep[1]=1,dfs(1,-1),dfs2(1,-1),prework();
        for(register int i=1;i<=m;i++){
            int u=read(),op1=read(),v=read(),op2=read();
            long long ans=getans(u,op1,v,op2);
            printf("%lld\n",ans>=inf?-1:ans);
        }
    }
}
/********************************************************************************************************************************************************************/
int main(){
    memset(head,-1,sizeof head);
    n=read(),m=read(),scanf("%s",shape);
    for(register int i=1;i<=n;i++) val[i]=read();
    for(register int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    //pts55::solve();
    //pts65::solve();
    pts100::solve();
    return 0;
}

评测结果