记录编号	545761	评测结果	AAAAAAAAAAATTTTTTETETEETT
题目名称	[NOIP 2018]保卫王国	最终得分	44
用户昵称	Hale	是否通过	未通过
代码语言	C++	运行时间	22.880 s
提交时间	2019-11-01 18:33:42	内存使用	16.91 MiB

#include<bits/stdc++.h>
#define I inline
#define LL long long
using namespace std;
const int N=1e5+7;
const int INF=2147483647;
int m,n,k,p[N];
int Q,head[N],cnt;
LL dp[N][2];
struct edge
{
	int nx,to;
} e[N];
void add_edge(int a,int b)
{
	cnt++;e[cnt].nx=head[a];e[cnt].to=b;head[a]=cnt;
}
bool limit[N],used[N];
I int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void dfs(int x,int fa)
{
	dp[x][1]+=p[x];
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==fa) continue;
		dfs(y,x);
		dp[x][1]+=min(dp[y][0],dp[y][1]);
		dp[x][0]+=dp[y][1];
	}
}
int main()
{
	freopen("2018defense.in","r",stdin);
	freopen("2018defense.out","w",stdout);
	//freopen("xx.in","r",stdin);
	n=read(),Q=read();string s1;cin>>s1;
	for (int i=1;i<=n;i++) p[i]=read();
	for (int i=1;i<n;i++)
	{
		int x=read(),y=read();
		add_edge(x,y);add_edge(y,x);
	}
	while (Q--)
	{
		int x=read(),a=read(),y=read(),b=read();
		memset(dp,0,sizeof(dp));
		dp[x][1-a]=INF;dp[y][1-b]=INF;
		dfs(1,-1);
		if (min(dp[1][0],dp[1][1])>=INF) printf("-1\n");
		else printf("%lld\n",min(dp[1][0],dp[1][1]));
	}
	return 0;
}