代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N=100010;
const long long INF=1e10;

void dfs1(int u);
void dfs2(int u);
void add(int u,int v);

int head[N],nxt[N<<1],to[N<<1],cnt;
long long n,m,p[N],f[N][2],g[N][2],bz[N][20][2][2],fa[N][20],dep[N],ans[2][2],anss[2][2][2],ansss;
char type[20];

int main()
{
    int i,u,v,a,b,x,y,cur=0;
    
    scanf("%lld%lld%s",&n,&m,type);
    
    for (i=1;i<=n;++i)
    {
        scanf("%lld",p+i);
    }
    
    for (i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    
    fa[1][0]=1;
    
    dfs1(1);
    dfs2(1);
    
    for (i=1;i<=16;++i)
    {
        for (u=1;u<=n;++u)
        {
            fa[u][i]=fa[fa[u][i-1]][i-1];
            bz[u][i][0][1]=min(bz[u][i-1][0][0]+bz[fa[u][i-1]][i-1][0][1],bz[u][i-1][0][1]+bz[fa[u][i-1]][i-1][1][1]);
            bz[u][i][1][0]=min(bz[u][i-1][1][0]+bz[fa[u][i-1]][i-1][0][0],bz[u][i-1][1][1]+bz[fa[u][i-1]][i-1][1][0]);
            bz[u][i][1][1]=min(bz[u][i-1][1][0]+bz[fa[u][i-1]][i-1][0][1],bz[u][i-1][1][1]+bz[fa[u][i-1]][i-1][1][1]);
            bz[u][i][0][0]=min(bz[u][i-1][0][0]+bz[fa[u][i-1]][i-1][0][0],bz[u][i-1][0][1]+bz[fa[u][i-1]][i-1][1][0]);
        }
    }
    
    while (m--)
    {
        scanf("%d%d%d%d",&a,&x,&b,&y);
        u=a;
        v=b;
        if (dep[u]<dep[v])
        {
            swap(u,v);
            swap(a,b);
            swap(x,y);
        }
        ans[cur][x]=f[u][x];
        ans[cur][x^1]=INF;
        for (i=16;i>=0;--i)
        {
            if ((dep[u]-dep[v])&(1<<i))
            {
                cur^=1;
                ans[cur][0]=min(bz[u][i][0][0]+ans[cur^1][0],bz[u][i][1][0]+ans[cur^1][1]);
                ans[cur][1]=min(bz[u][i][0][1]+ans[cur^1][0],bz[u][i][1][1]+ans[cur^1][1]);
                u=fa[u][i];
            }
        }
        if (u==v)
        {
            if (ans[cur][y]+g[u][y]>=INF)
            {
                puts("-1");
                continue;
            }
            printf("%lld\n",ans[cur][y]+g[u][y]);
            continue;
        }
        anss[cur][0][y]=ans[cur][0]+f[v][y];
        anss[cur][1][y]=ans[cur][1]+f[v][y];
        anss[cur][0][y^1]=anss[cur][1][y^1]=INF;
        for (i=16;i>=0;--i)
        {
            if (fa[u][i]!=fa[v][i])
            {
                cur^=1;
                anss[cur][0][0]=min(min(bz[u][i][0][0]+bz[v][i][0][0]+anss[cur^1][0][0],
                                        bz[u][i][1][0]+bz[v][i][0][0]+anss[cur^1][1][0]),
                                    min(bz[u][i][0][0]+bz[v][i][1][0]+anss[cur^1][0][1],
                                        bz[u][i][1][0]+bz[v][i][1][0]+anss[cur^1][1][1]));
                anss[cur][0][1]=min(min(bz[u][i][0][0]+bz[v][i][0][1]+anss[cur^1][0][0],
                                        bz[u][i][1][0]+bz[v][i][0][1]+anss[cur^1][1][0]),
                                    min(bz[u][i][0][0]+bz[v][i][1][1]+anss[cur^1][0][1],
                                        bz[u][i][1][0]+bz[v][i][1][1]+anss[cur^1][1][1]));
                anss[cur][1][0]=min(min(bz[u][i][0][1]+bz[v][i][0][0]+anss[cur^1][0][0],
                                        bz[u][i][1][1]+bz[v][i][0][0]+anss[cur^1][1][0]),
                                    min(bz[u][i][0][1]+bz[v][i][1][0]+anss[cur^1][0][1],
                                        bz[u][i][1][1]+bz[v][i][1][0]+anss[cur^1][1][1]));
                anss[cur][1][1]=min(min(bz[u][i][0][1]+bz[v][i][0][1]+anss[cur^1][0][0],
                                        bz[u][i][1][1]+bz[v][i][0][1]+anss[cur^1][1][0]),
                                    min(bz[u][i][0][1]+bz[v][i][1][1]+anss[cur^1][0][1],
                                        bz[u][i][1][1]+bz[v][i][1][1]+anss[cur^1][1][1]));
                u=fa[u][i];
                v=fa[v][i];
            }
        }
        ansss=min(min(min(anss[cur][0][0],anss[cur][0][1]),min(anss[cur][1][0],anss[cur][1][1]))+g[fa[u][0]][1]+f[fa[u][0]][1]-min(f[u][0],f[u][1])-min(f[v][0],f[v][1]),anss[cur][1][1]+g[fa[u][0]][0]+f[fa[u][0]][0]-f[u][1]-f[v][1]);
        if (ansss>=INF)
        {
            puts("-1");
            continue;
        }
        printf("%lld\n",ansss);
    }
    
    return 0;
}

void dfs1(int u)
{
    int i,v;
    f[u][1]=p[u];
    for (i=head[u];i;i=nxt[i])
    {
        v=to[i];
        if (v!=fa[u][0])
        {
            fa[v][0]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
            f[u][0]+=f[v][1];
            f[u][1]+=min(f[v][0],f[v][1]);
        }
    }
}

void dfs2(int u)
{
    int i,v;
    for (i=head[u];i;i=nxt[i])
    {
        v=to[i];
        if (v!=fa[u][0])
        {
            g[v][0]=g[u][1]+f[u][1]-min(f[v][0],f[v][1]);
            g[v][1]=min(g[u][0]+f[u][0]-f[v][1],g[u][1]+f[u][1]-min(f[v][0],f[v][1]));
            bz[v][0][0][1]=bz[v][0][1][1]=f[u][1]-min(f[v][0],f[v][1]);
            bz[v][0][1][0]=f[u][0]-f[v][1];
            bz[v][0][0][0]=INF;
            dfs2(v);
        }
    } 
}

void add(int u,int v)
{
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}

评测结果