代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,nx[200001],to[200001],head[100001],a,b,c,d,type;
int fa[200001],deep[200001],w[100001],jump[100001][18];
long long f[100001][2],g[100001][2],dp[100001][18][2][2],inf=2e15;
void read(int &x)
{
x=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
{
x=x*10+ch-'0';
ch=getchar();
}
}
void add(int u,int v,int d)
{
	nx[d]=head[u];
	to[d]=v;
	head[u]=d;
}
void build(int x)
{
	for(int i=head[x];i;i=nx[i])
		if(to[i]!=fa[x])
		{
			fa[to[i]]=x;
			deep[to[i]]=deep[x]+1;
			build(to[i]);
		}
}
void DP(int x)
{
	f[x][1]=w[x];
	if(x==a)
		f[x][(c+1)%2]=inf;
	if(x==b)
		f[x][(d+1)%2]=inf;
	for(int i=head[x];i;i=nx[i])
		if(to[i]!=fa[x])
		{
			int p=to[i];
			DP(p);
			f[x][1]+=min(f[p][0],f[p][1]);
			f[x][0]+=f[p][1];
		}
}
void D_P(int x)
{
	for(int i=head[x];i;i=nx[i])
		if(to[i]!=fa[x])
		{
			int p=to[i];
			g[p][0]=g[x][1]+f[x][1]-min(f[p][0],f[p][1]);
			g[p][1]=min(g[x][0]+f[x][0]-f[p][1],g[p][0]);
			D_P(p);
		}
}
long long work()
{
	if(deep[a]<deep[b])
	{
		swap(a,b);
		swap(c,d);
	}
	long long tx[2]={inf,inf},ty[2]={inf,inf},nx[2],ny[2];
	tx[c]=f[a][c],ty[d]=f[b][d];
	for(int i=17;i>=0;i--)
		if(deep[jump[a][i]]>=deep[b])
		{
			nx[0]=nx[1]=inf;
			for(int j=0;j<=1;j++)
				for(int k=0;k<=1;k++)
					nx[j]=min(nx[j],tx[k]+dp[a][i][k][j]);
			tx[0]=nx[0],tx[1]=nx[1];
			a=jump[a][i];
		}
	if(a==b)
		return tx[d]+g[b][d];
	for(int i=17;i>=0;i--)
		if(jump[a][i]!=jump[b][i])
		{
			nx[0]=nx[1]=inf;
			ny[0]=ny[1]=inf;
			for(int j=0;j<=1;j++)
				for(int k=0;k<=1;k++)
				{
					nx[j]=min(nx[j],tx[k]+dp[a][i][k][j]);
					ny[j]=min(ny[j],ty[k]+dp[b][i][k][j]);
				}
			tx[0]=nx[0],tx[1]=nx[1];
			ty[0]=ny[0],ty[1]=ny[1];
			a=jump[a][i];
			b=jump[b][i];
		}
	int lca=fa[a];
	return min(f[lca][0]-f[a][1]-f[b][1]+tx[1]+ty[1]+g[lca][0],f[lca][1]-min(f[a][0],f[a][1])-min(f[b][0],f[b][1])+min(tx[0],tx[1])+min(ty[0],ty[1])+g[lca][1]);
}
int main()
{
read(n),read(m),read(type);
	int u,v;
	for(int i=1;i<=n;i++)
read(w[i]);
	for(int i=1;i<n;i++)
	{
read(u),read(v);
		add(u,v,i);
		add(v,u,i+n);
	}
	deep[1]=1;
	build(1);
	DP(1);
	D_P(1);
	for(int i=1;i<=n;i++)
	{
		jump[i][0]=fa[i];
		dp[i][0][0][0]=2e15;
		dp[i][0][0][1]=f[fa[i]][1]-min(f[i][0],f[i][1]);
		dp[i][0][1][0]=f[fa[i]][0]-f[i][1];
		dp[i][0][1][1]=f[fa[i]][1]-min(f[i][0],f[i][1]);
	}
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
			for(int k=0;k<=1;k++)
				for(int l=0;l<=1;l++)
				{
					dp[i][j][k][l]=2e15;
					for(int q=0;q<=1;q++)
						dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-1][k][q]+dp[jump[i][j-1]][j-1][q][l]);
				}
		}
	for(int i=1;i<=m;i++)
	{
read(a),read(c),read(b),read(d);
		if((fa[a]==b&&c==0&&d==0)||(fa[b]==a&&c==0&&d==0))
		{
			cout<<"-1\n";
			continue;
		}
		cout<<work()<<endl;
	}
}

评测结果