代码

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
#define maxn 100005
#define inf (1ll<<60)
int n,m;
struct edge{
	int to,nxt;
}e[maxn<<1];
int tot,head[maxn];
inline void adde(int u,int v){
	e[++tot]=(edge){v,head[u]};
	head[u]=tot;
}

set<int>st[maxn];
int a[maxn];
int fa[maxn][20],dep[maxn];
int f[maxn][2],ancf[maxn][2],dp[maxn][20][2][2];
void dfs1(int u,int pa)
{
	fa[u][0]=pa,dep[u]=dep[pa]+1;
	f[u][1]=a[u];
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==pa)continue;
		dfs1(v,u);
		f[u][0]+=f[v][1];
		f[u][1]+=min(f[v][0],f[v][1]);
	}
}
void dfs2(int u)
{
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa[u][0])continue;
		ancf[v][0]=ancf[u][1]+f[u][1]-min(f[v][0],f[v][1]);
		ancf[v][1]=min(ancf[v][0],ancf[u][0]+f[u][0]-f[v][1]);
        dfs2(v);
	}
}

int solve(int u,int a,int v,int b)
{
	if(dep[u]<dep[v])swap(u,v),swap(a,b);
	int dpu[2]={inf,inf},dpv[2]={inf,inf},gu[2],gv[2];
	dpu[a]=f[u][a];
	dpv[b]=f[v][b];
	Rep(i,19,0)
		if(dep[fa[u][i]]>=dep[v])
		{
			gu[0]=gu[1]=inf;
			For(x,0,1)For(y,0,1)
				gu[x]=min(gu[x],dpu[y]+dp[u][i][y][x]);
			dpu[0]=gu[0];dpu[1]=gu[1];u=fa[u][i];
		}
	if(u==v)return dpu[b]+ancf[v][b];
	Rep(i,19,0){
		if(fa[u][i]==fa[v][i])continue;
		gu[0]=gu[1]=gv[0]=gv[1]=inf;
		For(x,0,1) For(y,0,1)
		{
			gu[x]=min(gu[x],dpu[y]+dp[u][i][y][x]);
			gv[x]=min(gv[x],dpv[y]+dp[v][i][y][x]);
		}
		dpu[0]=gu[0],dpu[1]=gu[1];
		dpv[0]=gv[0],dpv[1]=gv[1];
		u=fa[u][i],v=fa[v][i];
	}
	int lca=fa[u][0];
	return min(
		f[lca][0]+ancf[lca][0]-f[u][1]-f[v][1]+dpu[1]+dpv[1],
		f[lca][1]+ancf[lca][1]-min(f[u][0],f[u][1])-min(f[v][0],f[v][1])
							  +min(dpu[0],dpu[1])+min(dpv[0],dpv[1])
	);
} 


signed main()
{
	n=read(),m=read();read();
	For(i,1,n)a[i]=read();
	For(i,2,n){
		int u=read(),v=read();
		adde(u,v),adde(v,u);
		st[u].insert(v),st[v].insert(u);
	}
	dfs1(1,0),dfs2(1);
//	memset(dp,32,sizeof dp);
	For(i,1,n)
	{
		//    自己 祖先 
		int pa=fa[i][0];
		dp[i][0][0][0]=inf;
		dp[i][0][0][1]=f[pa][1]-min(f[i][0],f[i][1]);
		dp[i][0][1][0]=f[pa][0]-f[i][1];
		dp[i][0][1][1]=f[pa][1]-min(f[i][0],f[i][1]);
	}
	For(j,1,19)
		For(i,1,n)
		{
			int pa=fa[i][j-1];
			fa[i][j]=fa[fa[i][j-1]][j-1];
			For(x,0,1)For(y,0,1)dp[i][j][x][y]=inf;
			For(x,0,1)For(y,0,1)For(w,0,1)
				dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][j-1][x][w]+dp[pa][j-1][w][y]);
		}
	For(i,1,m)
	{
		int u=read(),x=read(),v=read(),y=read();
		if(!x&&!y&&st[u].count(v))puts("-1");
		else cout<<solve(u,x,v,y)<<endl;
	}
    return 0;
}

评测结果