全局平衡二叉树，直接维护最小点覆盖，状态 $\begin{pmatrix} inf & g_{i,0}\\ g_{i,1} & g_{i,1} \end{pmatrix}$，没特判叶子，所以答案是 $\begin{pmatrix} mat_{0,1}\\ mat_{1,1} \end{pmatrix}$,修改是p[i] $\pm inf$,48 pts 只过非树 Sub,但能过样例很奇怪O.o

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18;
int n,m,Ans;
string s;
int v[1000005];
int head[1000005],tot;
struct node{int nex,to;} edge[1000005<<1];
inline void add(int x,int y){edge[++tot]=(node){head[x],y};head[x]=tot;}
int f[1000005][2],fa[1000005],son[1000005],dfn[1000005],rk[1000005];
int siz[1000005],top[1000005],tail[1000005];
int lsiz[1000005];
struct matrix{int p[2][2];} g[1000005];
matrix operator *(matrix b,matrix a)
{
	matrix s;
	s.p[0][0] = min(b.p[0][0]+a.p[0][0],b.p[0][1]+a.p[1][0]);
	s.p[0][1] = min(b.p[0][0]+a.p[0][1],b.p[0][1]+a.p[1][1]);
	s.p[1][0] = min(b.p[1][0]+a.p[0][0],b.p[1][1]+a.p[1][0]);
	s.p[1][1] = min(b.p[1][0]+a.p[0][1],b.p[1][1]+a.p[1][1]);
	return s;
}
//----------------------GBT---------------------- 
namespace ciel
{
	int F[1000005],ch[1000005][2],root[1000005];
	matrix mat[1000005];
	inline void pushup(int x)
	{
		if (!ch[x][0] || !ch[x][1])
		{
			if (ch[x][0]) mat[x] = mat[ch[x][0]]*g[x];
			else if (ch[x][1]) mat[x] = g[x]*mat[ch[x][1]];
			else mat[x] = g[x];
		}
		else
			mat[x] = mat[ch[x][0]]*g[x]*mat[ch[x][1]];
	}
	inline bool isroot(int x){return ch[F[x]][0]!=x&&ch[F[x]][1]!=x;}
	int build(int l,int r,int lim)
	{
		if (l > r) return 0;
		int res = (lsiz[r]+(l>lim)*lsiz[l-1])>>1;
		for (int i = l; i <= r; i++)
		{
			if (lsiz[i] > res)
			{
				ch[rk[i]][0] = build(l,i-1,lim);
				ch[rk[i]][1] = build(i+1,r,lim);
				if (ch[rk[i]][0]) F[ch[rk[i]][0]] = rk[i];
				if (ch[rk[i]][1]) F[ch[rk[i]][1]] = rk[i];
				pushup(rk[i]);
				return rk[i];
			}
		}
	}
	void init()
	{
		int g0,g1;
		for (int x = 1; x <= n; x++)
		{
			g0 = 0; g1 = v[x];
			for (int i = head[x]; i; i = edge[i].nex)
			{
				int v = edge[i].to;
				if (v == fa[x] || v == son[x]) continue;
				g0 += f[v][1]; g1 += min(f[v][1],f[v][0]);
			}
			g[x] = (matrix){inf,g0,g1,g1};
		}
		for (int i = 1; i <= n; i++)
			if (top[i] == i)
				root[i] = build(dfn[i],dfn[tail[i]],dfn[i]),F[root[i]] = fa[i];
	}
	void modify(int x,int val)
	{
		g[x].p[1][0] = g[x].p[1][1] += val;
		v[x] += val;
		while (x)
		{
			if (F[x] && isroot(x))
			{
				g[F[x]].p[1][1] = g[F[x]].p[1][0]-=min(mat[x].p[1][1],mat[x].p[0][1]);
				g[F[x]].p[0][1] -= mat[x].p[1][1];
				pushup(x);
				g[F[x]].p[1][1] = g[F[x]].p[1][0]+=min(mat[x].p[1][1],mat[x].p[0][1]);
				g[F[x]].p[0][1] += mat[x].p[1][1];
			}
			else
			    pushup(x);
			x = F[x];
		}
	}
}
//-------------------------熟练剖分------------------------ 
namespace elia
{
	void dfs1(int x,int Fa)
	{
		fa[x] = Fa;
		siz[x] = 1;
		for (int i = head[x]; i; i = edge[i].nex)
		{
			int v = edge[i].to;
			if (v == Fa) continue;
			dfs1(v,x);
			siz[x] += siz[v];
			if (siz[v] > siz[son[x]])
				son[x] = v;
		}
	}
	void dfs2(int x,int tp)
	{
		top[x] = tp;
		dfn[x] = ++tot; rk[tot] = x;
		lsiz[dfn[x]] = (x!=tp)*lsiz[dfn[x]-1]+siz[x]-siz[son[x]];
		if (son[x]) dfs2(son[x],tp),tail[x] = tail[son[x]];
		else tail[x] = x;
		for (int i = head[x]; i; i = edge[i].nex)
			if (edge[i].to != fa[x] && edge[i].to != son[x])
				dfs2(edge[i].to,edge[i].to);
	}
	void DP(int x)
	{
		f[x][1] = v[x]; f[x][0] = 0;
		for (int i = head[x]; i; i = edge[i].nex)
		{
			int v = edge[i].to;
			if (v == fa[x]) continue;
			DP(v);
			f[x][1] += f[v][0];
			f[x][0] += min(f[v][1],f[v][0]);
		}
	}
	void init(){tot=0;dfs1(1,0);dfs2(1,1);DP(1);ciel::init();}
}
signed main()
{
	cin>>n>>m>>s;
	for (int i = 1; i <= n; i++) cin>>v[i];
	for (int i = 1,u,v; i < n; i++)
		cin>>u>>v,add(u,v),add(v,u);
	elia::init();
	int a,x,b,y;
	while (m--)
	{
		cin>>a>>x>>b>>y;
		if (!x && !y && (fa[a]==b||fa[b]==a))
		{
			puts("-1");
			continue;
		}
		ciel::modify(a,x==0?inf:-inf);
		ciel::modify(b,y==0?inf:-inf);
		Ans = min(ciel::mat[ciel::root[1]].p[1][1],ciel::mat[ciel::root[1]].p[0][1])+((x==1)+(y==1))*inf;
		cout<<Ans<<'\n';
		ciel::modify(a,x==1?inf:-inf);
		ciel::modify(b,y==1?inf:-inf);
	}
	return 0;
}