代码

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100000
#define M 100000
#define INF 1000000000000ll
int n,m;
int a[N+1];
struct EDGE{
	int to;
	EDGE *las;
} e[N*2+1];
int ne;
EDGE *last[N+1];
long long f[N+1][3],g[N+1][2];
void init1(int x,int fa){
	f[x][0]=0,f[x][1]=a[x];
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa){
			init1(ei->to,x);
			f[x][0]+=f[ei->to][1];
			f[x][1]+=f[ei->to][2];
		}
	f[x][2]=min(f[x][0],f[x][1]);
}
void init2(int x,int fa){
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa){
			g[ei->to][0]=g[x][1]+(f[x][1]-f[ei->to][2]);
			g[ei->to][1]=min(g[x][0]+(f[x][0]-f[ei->to][1]),g[ei->to][0]);
			init2(ei->to,x);
		}
}
struct Query{
	int a,x,b,y;
	int lca;
} q[M+1];
struct list{
	int v;
	list *lst;
} d[M*3+1];//这是链表开的内存池
int cnt;
list *qv[N+1],*ql[N+1];//qv[u]表示与u有关的询问 ql[u]表示lca为u的询问
inline void insert(list * &end,int v){
	++cnt;
	d[cnt].v=v,d[cnt].lst=end;
	end=d+cnt;
}
int top[N+1];//表示并查集上的父亲（我才不喜欢打fa）
long long h[N+1][4];//表示的时候直接压位了……自认为好打一些
inline void merge(int down,int up){//合并操作，将h[down]变为h[down]+h[up]
	static long long res[4];
	res[0]=min(h[up][0]-f[up][0]+h[down][0],h[up][1]-f[up][1]+h[down][2]);
	res[1]=min(h[up][0]-f[up][0]+h[down][1],h[up][1]-f[up][1]+h[down][3]);
	res[2]=min(h[up][2]-f[up][0]+h[down][0],h[up][3]-f[up][1]+h[down][2]);
	res[3]=min(h[up][2]-f[up][0]+h[down][1],h[up][3]-f[up][1]+h[down][3]);
	memcpy(&h[down],res,sizeof res);
}
void gettop(int x){
	if (top[top[x]]==top[x])
		return;
	gettop(top[x]);
	merge(x,top[x]);//在gettop过程中，合并两个答案信息
	top[x]=top[top[x]];
}
void dfs(int,int);
long long ans[N+1];
int main(){
	scanf("%d%d%*s",&n,&m);
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for (int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		++ne;
		e[ne].to=v,e[ne].las=last[u],last[u]=e+ne;
		++ne;
		e[ne].to=u,e[ne].las=last[v],last[v]=e+ne;
	}
	init1(1,0);
	init2(1,0);
	for (int i=1;i<=m;++i){
		scanf("%d%d%d%d",&q[i].a,&q[i].x,&q[i].b,&q[i].y);
		insert(qv[q[i].a],i);
		insert(qv[q[i].b],i);
	}
	dfs(1,0);
	for (int i=1;i<=m;++i)
		printf("%lld\n",ans[i]>=INF?-1:ans[i]);
	return 0;
}
void dfs(int x,int fa){
	top[x]=x;
	for (list *i=qv[x];i;i=i->lst){
		int u=q[i->v].a^q[i->v].b^x;//表示a,b中除了x以外的另一个数
		if (!top[u])
			continue;
		gettop(u);
		q[i->v].lca=top[u];//求出LCA
		insert(ql[q[i->v].lca],i->v);//将询问挂在LCA上
	}
	for (EDGE *ei=last[x];ei;ei=ei->las)
		if (ei->to!=fa){
			dfs(ei->to,x);
			//一坨初始化，具体解释见上
			h[ei->to][0]=INF;
			h[ei->to][1]=f[x][0]-f[ei->to][1]+f[ei->to][1];
			h[ei->to][2]=f[x][1]-f[ei->to][2]+f[ei->to][0];
			h[ei->to][3]=f[x][1]-f[ei->to][2]+f[ei->to][1];
			top[ei->to]=x;
		}
	for (list *i=ql[x];i;i=i->lst){
		int a=q[i->v].a,b=q[i->v].b;
		gettop(a),gettop(b);
		//具体解释见上
		if (x==a)
			ans[i->v]=h[b][q[i->v].x<<1|q[i->v].y]+g[a][q[i->v].x];
		else if (x==b)
			ans[i->v]=h[a][q[i->v].y<<1|q[i->v].x]+g[b][q[i->v].y];
		else
			ans[i->v]=min(h[a][0<<1|q[i->v].x]+h[b][0<<1|q[i->v].y]-f[x][0]+g[x][0],h[a][1<<1|q[i->v].x]+h[b][1<<1|q[i->v].y]-f[x][1]+g[x][1]);
	}
}

评测结果