代码

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const int MAX=1e5+10;
const LL llinf=(1ll<<55);
class Tree{
    int fir[MAX],stt[20][MAX*2],lg2[MAX*2],tail;
    void dfs(int now,int fa){
        dep[now]=(~fa)?dep[fa]+1:1;
        fir[now]=tail,stt[0][tail++]=now;
        for(int i=head[now];~i;i=e[i].nxt){
            int to=e[i].to;
            if(to==fa)continue;
            dfs(to,now),stt[0][tail++]=now;
        }
    }
    public:
    struct Edge{int to,nxt;}e[MAX*2];
    int head[MAX],m;
    int dep[MAX];
    void reset(){
        memset(head,-1,sizeof(head));m=0;
    }
    Tree(){reset();}
    void addedge(int fr,int to){e[m].to=to,e[m].nxt=head[fr],head[fr]=m++;}
    void addtwo(int u,int v){
        addedge(u,v),addedge(v,u);
    }
    inline int shallower(int u,int v){return (dep[u]<dep[v])?u:v;}
    void prework(int rt){
        tail=0;
        dfs(rt,-1);
        lg2[1]=0;for(int i=2;i<tail;++i)lg2[i]=lg2[i/2]+1;
        for(int i=1;(1<<i)<tail;++i){
            for(int j=0;j+(1<<i)<tail;++j){
                stt[i][j]=shallower(stt[i-1][j],stt[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int lca(int u,int v){
        if(fir[u]>fir[v])swap(u,v);
        int i=lg2[fir[v]-fir[u]+1];
        return shallower(stt[i][fir[u]],stt[i][fir[v]-(1<<i)+1]);
    }
};
Tree tr;
int n,m;
LL val[MAX],all;
LL up[MAX][2],down[MAX][2],sum[20][MAX][2][2];
int anc[20][MAX];
void getdown(int now,int fa){
    anc[0][now]=fa;
    down[now][0]=0,down[now][1]=val[now];
    for(int i=tr.head[now];~i;i=tr.e[i].nxt){
        int to=tr.e[i].to;
        if(to==fa)continue;
        getdown(to,now);
        down[now][0]+=down[to][1],down[now][1]+=min(down[to][0],down[to][1]);
    }
}
void getup(int now,int fa){
    for(int i=tr.head[now];~i;i=tr.e[i].nxt){
        int to=tr.e[i].to;
        if(to==fa)continue;
        up[to][0]=up[now][1]+down[now][0]-down[to][1];
        up[to][1]=min(up[now][0],up[now][1])+down[now][1]-min(down[to][0],down[to][1]);
        getup(to,now);
    }
}
void binadd(){
    for(int i=1;i<=n;++i){
        sum[0][i][0][1]=sum[0][i][1][1]=down[anc[0][i]][1]-min(down[i][0],down[i][1]);
        sum[0][i][1][0]=down[anc[0][i]][0]-down[i][1];
        sum[0][i][0][0]=llinf;
    }
    for(int i=1;(1<<i)<=n;++i){
        for(int j=1;j<=n;++j){
            anc[i][j]=anc[i-1][anc[i-1][j]];
            for(int k=0;k<2;++k){
                for(int l=0;l<2;++l){
                    int en=anc[i-1][j];
                    sum[i][j][k][l]=min(sum[i-1][j][k][0]+sum[i-1][en][0][l],sum[i-1][j][k][1]+sum[i-1][en][1][l]);
                }
            }
        }
    }
}
int goup(int now,int k){
    for(int i=0;(1<<i)<=k;++i){
        if((1<<i)&k)now=anc[i][now];
    }
    return now;
}
LL path(int now,bool x,int en,bool y){
    if(tr.dep[now]<tr.dep[en])swap(now,en),swap(x,y);
    int k=tr.dep[now]-tr.dep[en];
    if(now==en){
        if(x!=y)return llinf;
        return 0;
    }
    LL ret[2];
    ret[0]=ret[1]=0;
    for(int i=0;(1<<i)<=k;++i){
        if((1<<i)&k){
            if(ret[0]==0&&ret[1]==0){
                ret[0]=sum[i][now][x][0],ret[1]=sum[i][now][x][1];
            }
            else{ 
                LL tmp[2];
                tmp[0]=ret[0],tmp[1]=ret[1];
                ret[0]=min(tmp[0]+sum[i][now][0][0],tmp[1]+sum[i][now][1][0]);
                ret[1]=min(tmp[0]+sum[i][now][0][1],tmp[1]+sum[i][now][1][1]);
            }
            now=anc[i][now];
        }
    }
    return ret[y];
}
LL ans(int u,bool x,int v,bool y){
    int lca=tr.lca(u,v);
    if(lca==u||lca==v){
        if(lca==u)swap(u,v),swap(x,y);
        return path(u,x,v,y)+down[u][x]+((y==0)?up[v][1]:min(up[v][0],up[v][1]));
    }
    int enu=goup(u,tr.dep[u]-tr.dep[lca]-1),env=goup(v,tr.dep[v]-tr.dep[lca]-1);
    LL ret=llinf;
    if((enu!=u||x==1)&&(env!=v||y==1)){
        ret=up[lca][1]+down[lca][0]-down[enu][1]-down[env][1]+down[u][x]+down[v][y]+path(u,x,enu,1)+path(v,y,env,1);
    }
    LL tmp=min(up[lca][0],up[lca][1])+down[u][x]+down[v][y]+down[lca][1]-min(down[enu][0],down[enu][1])-min(down[env][0],down[env][1]);
    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            ret=min(ret,tmp+path(u,x,enu,i)+path(v,y,env,j));
        }
    }
    return ret;
}
void init(){
    all=0;
    up[0][0]=up[0][1]=down[0][0]=down[0][1]=llinf;
}
namespace n2{
    LL dp[MAX][2];
    void dfs(int now,int fa){
        if(dp[now][1]==0)dp[now][1]=val[now];
        for(int i=tr.head[now];~i;i=tr.e[i].nxt){
            int to=tr.e[i].to;
            if(to==fa)continue;
            dfs(to,now);
            dp[now][0]+=dp[to][1];
            dp[now][1]+=min(dp[to][0],dp[to][1]);
        }
    }
    LL ans(int u,bool x,int v,bool y){
        memset(dp,0,sizeof(dp));
        dp[u][!x]=dp[v][!y]=llinf;
        dfs(1,0);
        LL ret=min(dp[1][0],dp[1][1]);
        if(ret>all)ret=-1;
        return ret;
    }
}
int main(){
    char ty[10];
    scanf("%d%d%s",&n,&m,ty);
    init();
    for(int i=1;i<=n;++i)scanf("%lld",&val[i]),all+=val[i];
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        tr.addtwo(u,v);
    }
    tr.prework(1);
    getdown(1,0),getup(1,0);
    binadd();
    for(int i=1;i<=m;++i){
        int u,x,v,y;
        scanf("%d%d%d%d",&u,&x,&v,&y);
        LL tmp=ans(u,x,v,y);
        if(tmp>all)tmp=-1;
        printf("%lld\n",tmp);
        //printf("%lld\n",n2::ans(u,x,v,y));
    }
    return 0;
}

评测结果