代码

#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#define meow(args...) fprintf(stderr, args)
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}

typedef long long Vector[2], Matrix[2][2];
struct Query {
	int a, b, x, y, lca;
	long long ans;
	Query *next;
};

const int N=1e5+5;
const long long INFTY=1e18;

Vector f[N];
Query q[N], *list[N];
Matrix unit, trans[N], partial[N], w[N];
int n, m, p[N], head[N], to[N<<1], next[N<<1], dfsclock, dfn[N], dfo[N], up[N];

int read() {
	int a=0;
	unsigned char c;
	while((c=getchar()-'0')>9);
	while(a=a*10+c, (c=getchar()-'0')<=9);
	return a;
}

void mul(Matrix a, Matrix b, Matrix c) {
	Matrix ans={};
	ans[0][0]=std::min(a[0][0]+b[0][0], a[0][1]+b[1][0]);
	ans[0][1]=std::min(a[0][0]+b[0][1], a[0][1]+b[1][1]);
	ans[1][0]=std::min(a[1][0]+b[0][0], a[1][1]+b[1][0]);
	ans[1][1]=std::min(a[1][0]+b[0][1], a[1][1]+b[1][1]);
	memcpy(c, ans, sizeof(ans));
}
void mul(Matrix a, Vector b, Vector c) {
	Vector ans={};
	ans[0]=std::min(a[0][0]+b[0], a[0][1]+b[1]);
	ans[1]=std::min(a[1][0]+b[0], a[1][1]+b[1]);
	memcpy(c, ans, sizeof(ans));
}

int top(int u) {
	if(u==up[u]) return u;
	int v=top(up[u]);
	mul(w[up[u]], w[u], w[u]);
	return up[u]=v;
}
int fast_top(int u) {return u==up[u]?u:(up[u]=fast_top(up[u]));}

void plain_dp(int u, int fa) {
	dfo[dfn[u]=dfsclock++]=u;
	f[u][0]=0;
	f[u][1]=p[u];
	for(int i=head[u], *ptr=head+u; ~i; i=next[i]) {
		int v=to[i];
		if(v==fa) {
			*ptr=next[i];
			continue;
		}
		plain_dp(v, u);
		f[u][0]+=f[v][1];
		f[u][1]+=std::min(f[v][0], f[v][1]);
		ptr=next+i;
	}
}
void find_lca(int u) {
	for(int i=head[u]; ~i; i=next[i]) {
		find_lca(to[i]);
		up[to[i]]=u;
	}
	for(Query *i=list[u]; i; i=i->next) i->lca=fast_top(i->a);
}
void solve(int u) {
	for(int i=head[u]; ~i; i=next[i]) solve(to[i]);
	for(Query *i=list[u]; i; i=i->next)
		if(i->a!=u) {
			Vector fa, fb, fu;
			int atop=top(i->a), btop=top(i->b);
			memcpy(fa, f[i->a], sizeof(Vector));
			memcpy(fb, f[i->b], sizeof(Vector));
			fa[!i->x]=fb[!i->y]=INFTY;
			mul(w[i->a], fa, fa);
			mul(w[i->b], fb, fb);
			fu[0]=f[u][0]+fa[1]-f[atop][1]+fb[1]-f[btop][1];
			fu[1]=f[u][1]+std::min(fa[0], fa[1])-std::min(f[atop][0], f[atop][1])+std::min(fb[0], fb[1])-std::min(f[btop][0], f[btop][1]);
			mul(partial[u], fu, fu);
			i->ans=std::min(fu[0], fu[1]);
		} else {
			Vector curf;
			int btop=top(i->b);
			memcpy(curf, f[i->b], sizeof(Vector));
			curf[!i->y]=INFTY;
			mul(w[i->b], curf, curf);
			mul(trans[btop], curf, curf);
			curf[!i->x]=INFTY;
			mul(partial[u], curf, curf);
			i->ans=std::min(curf[0], curf[1]);
		}
	for(int i=head[u]; ~i; i=next[i]) {
		up[to[i]]=u;
		memcpy(w[to[i]], trans[to[i]], sizeof(Matrix));
	}
}

int main() {
	unit[0][0]=unit[1][1]=0;
	unit[0][1]=unit[1][0]=INFTY;
	n=read(), m=read(), read();
	for(int i=1; i<=n; ++i) p[i]=read();
	memset(head+1, -1, n*sizeof(int));
	for(int i=1, j=0; i<n; ++i) {
		int u=read(), v=read();
		to[j]=v, next[j]=head[u], head[u]=j++;
		to[j]=u, next[j]=head[v], head[v]=j++;
	}
	plain_dp(1, -1);
	memcpy(partial[1], unit, sizeof(unit));
	for(int t=0; t<n; ++t) {
		int u=dfo[t];
		for(int i=head[u]; ~i; i=next[i]) {
			int v=to[i];
			trans[v][0][0]=INFTY;
			trans[v][0][1]=f[u][0]-f[v][1];
			trans[v][1][0]=trans[v][1][1]=f[u][1]-std::min(f[v][0], f[v][1]);
			mul(partial[u], trans[v], partial[v]);
		}
	}
	for(Query *i=q; i!=q+m; ++i) {
		int a=read(), x=read(), b=read(), y=read();
		if(dfn[a]>dfn[b]) std::swap(a, b), std::swap(x, y);
		i->a=a, i->x=x, i->b=b, i->y=y;
		i->next=list[b], list[b]=i;
	}
	for(int i=1; i<=n; ++i) up[i]=i;
	find_lca(1);
	memset(list+1, 0, n*sizeof(Query *));
	for(Query *i=q; i!=q+m; ++i) i->next=list[i->lca], list[i->lca]=i;
	for(int i=1; i<=n; ++i) {
		up[i]=i;
		memcpy(w[i], unit, sizeof(unit));
	}
	solve(1);
	for(Query *i=q; i!=q+m; ++i) printf("%lld\n", i->ans>1e17?-1ll:i->ans);
	return 0;
}

评测结果