第一发交的时候 96pts (WA On #22)，于是下载了 #22 的样例并 freopen 在本地运行，然后居然 RE 了。后面把 #22 改对了（指洛谷上提交能 AC），在本地测依然还是会 RE。$10^5$ 应该是不会有爆栈的可能的吧？

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

inline int read(){
	int ret=0;
	char ch=' ',c=getchar();
	while(!('0'<=c&&c<='9')) ch=c,c=getchar();
	while('0'<=c&&c<='9') ret=(ret<<1)+(ret<<3)+(c^48),c=getchar();
	return ch=='-'?-ret:ret;
}

int n,m;
const int N=1e5+10,M=2e5+10;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int val[N];

struct mat{
	ll a[2][2];
	mat(){}
	mat(ll _1,ll _2,ll _3,ll _4){
		a[0][0]=_1;
		a[0][1]=_2;
		a[1][0]=_3;
		a[1][1]=_4;
	}
	inline ll* operator[] (const int x){ return a[x]; }
	inline mat operator* (mat& b) const{
		static mat c;
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				c[i][j]=INF;
				for(int k=0;k<2;k++){
					c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
				}
			}
		}
		return c;
	}
};

inline void show(mat &mt){
	if(mt[0][0]>=INF) printf("F");
	else printf("%lld",mt[0][0]);
	printf(" %lld\n%lld %lld\n",mt[0][1],mt[1][0],mt[1][1]);
}

int to[M],nt[M],idx,h[N];
inline void add(int x,int y){
	to[idx]=y;
	nt[idx]=h[x];
	h[x]=idx++;
}

int dad[N];
int son[N],sz[N];
void dfs1(int u,int fa){
	dad[u]=fa;
	sz[u]=1;
	int id=-1,ma=0;
	for(int i=h[u];i!=-1;i=nt[i]){
		int j=to[i];
		if(j==fa) continue;
		dfs1(j,u);
		sz[u]+=sz[j];
		if(ma<sz[j]) id=j,ma=sz[j];
	}
	son[u]=id;
}

int timestamp=0;
int dfn[N],nw[N];
int top[N],low[N];
void dfs2(int u,int t){
	top[u]=t;
	dfn[u]=++timestamp;
	nw[timestamp]=u;
	if(~son[u]) dfs2(son[u],t);
	else{
		low[t]=u;
		return ;
	}
	for(int i=h[u];i!=-1;i=nt[i]){
		int j=to[i];
		if(j==dad[u]||j==son[u]) continue;
		dfs2(j,j);
	}
}

ll g[N][2];
struct NODE{
	int l,r;
	mat mt;
} tr[N<<2];

inline void pushup(NODE &root,NODE &zuo,NODE &you){
	root.mt=you.mt*zuo.mt;
}
inline void pushup(int u){
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r){
	tr[u]=(NODE){l,r};
	if(l==r){
		tr[u].mt=mat(INF,0,0,0);
		return ;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}

void modify(int u,int k){
	if(tr[u].l==tr[u].r){
		int i=nw[k];
		tr[u].mt=mat(INF,g[i][1],g[i][0],g[i][1]);
//		printf("md %d:\n",i),show(tr[u].mt);
		return ;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	if(k<=mid) modify(u<<1,k);
	else modify(u<<1|1,k);
	pushup(u);
}

mat query(int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].mt;
	mat ans;
	int mid=(tr[u].l+tr[u].r)>>1;
	if(r<=mid) ans=query(u<<1,l,r);
	else if(l>mid) ans=query(u<<1|1,l,r);
	else{
		mat zuo=query(u<<1,l,r);
		mat you=query(u<<1|1,l,r);
		ans=you*zuo;
	}
	return ans;
}

void modify_path(int u){
	static mat bef,aft;
	while(u){
//		printf("modify==%d->%d\n",top[u],low[top[u]]);
		mat bef=query(1,dfn[top[u]],dfn[low[top[u]]]);
//		printf("bef:\n"),show(bef);
		modify(1,dfn[u]);
		mat aft=query(1,dfn[top[u]],dfn[low[top[u]]]);
//		printf("aft:\n"),show(aft);
		u=dad[top[u]];
		if(!u) break;
		g[u][0]+=min(aft[0][1],aft[1][1])-min(bef[0][1],bef[1][1]);
		g[u][1]+=min(min(aft[0][0],aft[1][0]),min(aft[0][1],aft[1][1]))
				-min(min(bef[0][0],bef[1][0]),min(bef[0][1],bef[1][1]));
	}
}

ll query_path(){
	mat mt=query(1,dfn[1],dfn[low[1]]);
	ll ans=min(min(mt[0][0],mt[0][1]),min(mt[1][0],mt[1][1]));
	if(ans>=INF) return -1ll;
	else return ans;
}

int main(){
//	freopen("P5024_22.in","r",stdin);
	n=read(),m=read();read();
	for(int i=1;i<=n;i++) val[i]=read();
	memset(h,-1,sizeof(h));
	int x,y;
	for(int i=1;i<n;i++){
		x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=n;i++){
		g[i][1]+=val[i];
		modify_path(i);
//		printf("=====insert %d=====\n",i);
//		for(int i=1;i<=n;i++){
//			printf("%d: g0=%d g1=%d\n",i,g[i][0],g[i][1]);
//		}
	}
	int x_1,y_1,x_2,y_2;
	ll bef_1,bef_2;
	while(m--){
		x_1=read(),y_1=read();
		x_2=read(),y_2=read();
		bef_1=g[x_1][y_1^1];
		bef_2=g[x_2][y_2^1];
		g[x_1][y_1^1]=INF;
		modify_path(x_1);
		g[x_2][y_2^1]=INF;
		modify_path(x_2);
		printf("%lld\n",query_path());
		g[x_1][y_1^1]=bef_1;
		modify_path(x_1);
		g[x_2][y_2^1]=bef_2;
		modify_path(x_2);
	}
	return 0;
}