可以直接套动态dp，但因为它询问之间相互独立，所以可以直接倍增记x转移到fa[x]的矩阵
#include<bits/stdc++.h>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
const int maxn=1e5+;
const ll inf=1e17; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,p[maxn];
int eg[maxn*][],egh[maxn],ect,fa[maxn][],dep[maxn];
ll f[maxn][];
struct Mat{
int n,m;ll a[][];
Mat(int a0=,int a1=,ll a2=,ll a3=,ll a4=,ll a5=){
n=a0,m=a1;a[][]=a2,a[][]=a3,a[][]=a4,a[][]=a5;
}
}trans[maxn][]; inline Mat operator * (Mat a,Mat b){
Mat re;
re.n=a.n,re.m=b.m;
for(int i=;i<=re.n;i++){
for(int j=;j<=re.m;j++){
re.a[i][j]=inf;
for(int k=;k<=a.m;k++){
re.a[i][j]=min(re.a[i][j],a.a[i][k]+b.a[k][j]);
}
}
}return re;
} inline void adeg(int a,int b){
eg[++ect][]=b,eg[ect][]=egh[a],egh[a]=ect;
} void dfs1(int x){
f[x][]=,f[x][]=p[x];
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];if(b==fa[x][]) continue;
fa[b][]=x,dep[b]=dep[x]+;
dfs1(b);
f[x][]+=f[b][],f[x][]+=min(f[b][],f[b][]);
}
} void dfs2(int x){
if(fa[x][]){
ll s0,s1;
s0=f[fa[x][]][]-f[x][];
s1=f[fa[x][]][]-min(f[x][],f[x][]);
trans[x][]=Mat(,,inf,s1,s0,s1);
for(int i=;fa[x][i]&&fa[fa[x][i]][i];i++){
fa[x][i+]=fa[fa[x][i]][i];
trans[x][i+]=trans[x][i]*trans[fa[x][i]][i];
}
}
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];if(b==fa[x][]) continue;
dfs2(b);
}
} inline ll update(int x,int y,Mat &fx,Mat &fy){
for(int i=log2(dep[x]-dep[y]);i>=&&dep[x]!=dep[y];i--){
if(dep[fa[x][i]]>=dep[y])
fx=fx*trans[x][i],x=fa[x][i];
}
int lca;Mat fl;
if(x==y){
lca=y;fl=fx;
if(fy.a[][]==inf) fl.a[][]=inf;
else if(fy.a[][]==inf) fl.a[][]=inf;
}else{
for(int i=log2(dep[x]);i>=;i--){
if(fa[x][i]!=fa[y][i]){
fx=fx*trans[x][i],fy=fy*trans[y][i];
x=fa[x][i],y=fa[y][i];
}
}
lca=fa[x][];
// printf("~%d %d %d %d %d %d\n",x,fx.a[1][1],fx.a[1][2],y,fy.a[1][1],fy.a[1][2]);
ll a0=f[lca][]-f[x][]-f[y][]+fx.a[][]+fy.a[][];
ll a1=f[lca][]-min(f[x][],f[x][])-min(f[y][],f[y][])+min(fx.a[][],fx.a[][])+min(fy.a[][],fy.a[][]);
fl=Mat(,,a0,a1,,);
}
for(int i=log2(dep[lca]);i>=;i--){
if(fa[lca][i]){
fl=fl*trans[lca][i];
lca=fa[lca][i];
}
}
return min(fl.a[][],fl.a[][]);
} int main(){
// freopen("testdata.in","r",stdin);
int i,j,k;
N=rd(),M=rd();rd();
for(i=;i<=N;i++) p[i]=rd();
for(i=;i<N;i++){
int a=rd(),b=rd();
adeg(a,b);adeg(b,a);
}
dep[]=;dfs1();dfs2();
for(i=;i<=M;i++){
int a=rd(),x=rd(),b=rd(),y=rd();
if(dep[a]<dep[b]) swap(a,b),swap(x,y);
if(fa[a][]==b&&!x&&!y){
printf("-1\n");continue;
}
Mat fx,fy;
if(x) fx=Mat(,,inf,f[a][],,);
else fx=Mat(,,f[a][],inf,,);
if(y) fy=Mat(,,inf,f[b][],,);
else fy=Mat(,,f[b][],inf,,);
printf("%lld\n",update(a,b,fx,fy));
}
return ;
}