代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define min(x,y) (x<y?x:y)
typedef long long LL;
const int logn=18;
const int maxn=1e5+3;
const LL Inf=0x0101010101010101;
struct Matrix{
	LL a[2][2];
	inline void Init(){
		memset(a,0x01,sizeof(a));
	}
	inline void Set(LL x,LL xx,LL y,LL yy){
		a[0][0]=x,a[0][1]=xx;
		a[1][0]=y,a[1][1]=yy;
	}
	inline Matrix operator *(const Matrix&x)const{
		Matrix ans;ans.Init();
		register int i,j,k;
		for(i=0;i<2;++i)for(k=0;k<2;++k)for(j=0;j<2;++j)
			ans.a[i][j]=min(ans.a[i][j],a[i][k]+x.a[k][j]);
		return ans;
	}
//	inline void Print(){
//		printf("%lld %lld\n",a[0][0],a[0][1]);
//		printf("%lld %lld\n",a[1][0],a[1][1]);
//	}
}g[maxn][logn];
struct Road{
	int to;
	int last;
}a[maxn<<1];
int n;
int m;
int tot;
int d[maxn];
int v[maxn];
int bin[logn];
int son[maxn];
int top[maxn];
int haha[maxn];
int head[maxn];
int size[maxn];
LL dp[maxn][2];
int f[maxn][logn];
void Dfs1(int);
void Dfs2(int);
void HA(int,int);
int LCA(int,int);
int main(){
	bin[0]=1;
	for(int i=1;i<logn;++i)
		bin[i]=bin[i-1]<<1;
	char s[10];
	scanf("%d%d%s",&n,&m,s);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
	for(int i=1,x,y;i<n;++i)
		scanf("%d%d",&x,&y),HA(x,y),HA(y,x);
	Dfs1(1),top[1]=1,Dfs2(1);
//	printf("d:");
//	for(int i=1;i<=n;++i)
//		printf("%d ",d[i]);
//	puts("");
//	printf("top:");
//	for(int i=1;i<=n;++i)
//		printf("%d ",top[i]);
//	puts("");
	while(m--){
		int a,x,b,y;
		scanf("%d%d%d%d",&a,&x,&b,&y);
		int lca=LCA(a,b);Matrix A,B;
		if(b==lca)
			std::swap(a,b),std::swap(x,y);
		if(x)A.Set(Inf,Inf,dp[a][1],Inf);
		else A.Set(dp[a][0],Inf,Inf,Inf);
		if(y)B.Set(Inf,Inf,dp[b][1],Inf);
		else B.Set(dp[b][0],Inf,Inf,Inf);
//		A.Print(),B.Print();
		int len=d[a]-d[lca];
		if(len)for(int j=logn-1;~j;--j)
			if(len&bin[j])A=g[a][j]*A,a=f[a][j];
		len=d[b]-d[lca]-1;
		if(len)for(int j=logn-1;~j;--j)
			if(len&bin[j])B=g[b][j]*B,b=f[b][j];
//		printf("%d %d\n",a,b);
//		A.Print(),B.Print();
		A.a[0][0]-=dp[b][1];
		A.a[0][0]+=B.a[1][0];
//		printf("HAHA:%lld %lld\n",dp[b][1],B.a[1][0]);
		A.a[1][0]-=min(dp[b][0],dp[b][1]);
		A.a[1][0]+=min(B.a[0][0],B.a[1][0]);
//		A.Print();
		if(d[a])for(int j=logn-1;~j;--j)
			if(d[a]&bin[j])A=g[a][j]*A,a=f[a][j];
//		printf("a=%d\n",a);
		LL ans=min(A.a[0][0],A.a[1][0]);
		if(ans<1e12)printf("%lld\n",ans);
		else puts("-1");
	}
	return 0;
}
inline void HA(int x,int y){
	a[++tot].to=y;
	a[tot].last=head[x];
	head[x]=tot;
}
#define y a[i].to
inline void Dfs1(int x){
	size[x]=1;
	dp[x][0]=0,dp[x][1]=v[x];
	for(int i=head[x];i;i=a[i].last){
		if(y==haha[x])continue;
		haha[y]=x,d[y]=d[x]+1;
		Dfs1(y),size[x]+=size[y];
		dp[x][0]+=dp[y][1];
		dp[x][1]+=min(dp[y][0],dp[y][1]);
		if(size[y]>size[son[x]])son[x]=y;
	}
}
inline void Dfs2(int x){
	f[x][0]=haha[x];
	LL xx=dp[haha[x]][1]-min(dp[x][0],dp[x][1]);
	g[x][0].Set(Inf,dp[haha[x]][0]-dp[x][1],xx,xx);
	for(int j=1;bin[j]<=d[x];++j){
		f[x][j]=f[f[x][j-1]][j-1];
		g[x][j]=g[f[x][j-1]][j-1]*g[x][j-1];
	}
	if(son[x])top[son[x]]=top[x],Dfs2(son[x]);
	for(int i=head[x];i;i=a[i].last)
		if(y!=haha[x] && y!=son[x])top[y]=y,Dfs2(y);
}
#undef y
inline int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])std::swap(x,y);
		x=haha[top[x]];
	}return d[x]<d[y] ? x : y;
}

评测结果