44pts

#include<bits/stdc++.h>
using namespace std;

#define int long long  // 使用 long long 避免溢出

const int N = 2010, inf = 1e16;  // N: 最大节点数, inf: 无穷大

int n, m;           // n: 城市数, m: 询问数
int val[N];         // val[i]: 城市i驻扎军队的花费
int dp[N][2];       // dp[i][0]: 节点i不选时的最小花费, dp[i][1]: 节点i选时的最小花费
int ls, head[N];    // 链式前向星: ls是边的编号, head[u]是u的第一条边
string str;         // 数据类型(如A1, C3等), 本题中未使用

int a, X, b, Y;     // 当前询问: 城市a必须/不得驻扎(X=1必须, X=0不得), 城市b同理

// 边结构体: to是边的终点, net是下一条边的编号
struct edge {
    int to, net;
} s[N << 1];        // 无向图, 边数是节点数的两倍

// 添加一条从u到v的边
void add(int u, int v) {
    s[++ls] = (edge){v, head[u]};  // 新建边, 指向v, 头插法
    head[u] = ls;                   // 更新头指针
}

/*
 * DFS进行树形DP
 * x: 当前节点
 * y: 父节点(避免回溯)
 * 
 * 状态转移:
 * 1. 如果x不选(dp[x][0]), 则所有子节点u都必须选(dp[u][1])
 *    因为每条边至少要有一个端点被选
 * 2. 如果x选(dp[x][1]), 则子节点u可选可不选(取最小值)
 *    即 min(dp[u][0], dp[u][1])
 * 
 * 再加上强制约束: 如果当前节点有特殊要求, 将相反状态设为inf
 */
void dfs(int x, int y) {
    // 初始化: 不选花费为0, 选花费为val[x]
    dp[x][0] = 0;
    dp[x][1] = val[x];
    
    // 遍历所有子节点
    for (int i = head[x]; i; i = s[i].net) {
        int u = s[i].to;  // 子节点
        if (u == y) continue;  // 跳过父节点, 避免死循环
        
        dfs(u, x);  // 递归处理子节点
        
        // 状态转移
        dp[x][0] += dp[u][1];  // 当前节点不选 -> 子节点必须选
        dp[x][1] += min(dp[u][0], dp[u][1]);  // 当前节点选 -> 子节点可选可不选
    }
    
    /*
     * 强制约束处理:
     * 如果当前节点是a, 且要求X为0(不得驻扎), 则dp[a][1]=inf(不能选)
     * 如果当前节点是a, 且要求X为1(必须驻扎), 则dp[a][0]=inf(不能不选)
     * X^1 表示取反: 0变1, 1变0
     * 同理处理节点b
     */
    if (x == a) dp[x][X ^ 1] = inf;  // 强制要求X, 则相反状态不可用
    if (x == b) dp[x][Y ^ 1] = inf;
}

signed main() {
    // 输入数据
    scanf("%lld%lld", &n, &m);
    cin >> str;  // 读入数据类型(如A1, C3等), 本题未使用
    
    // 读入每个城市驻扎军队的花费
    for (int i = 1; i <= n; i++) scanf("%lld", &val[i]);
    
    // 读入n-1条边, 构建树
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        add(u, v);  // 添加双向边
        add(v, u);
    }
    
    // 处理每个询问
    for (int i = 1; i <= m; i++) {
        // 读入要求: 城市a驻扎X支军队, 城市b驻扎Y支军队
        // X=0表示不得驻扎, X=1表示必须驻扎
        scanf("%lld%lld%lld%lld", &a, &X, &b, &Y);
        
        // 从根节点1开始进行树形DP
        dfs(1, 0);
        
        // 取最小值: min(dp[1][0], dp[1][1])
        // 如果小于inf则输出答案, 否则输出-1(无法满足要求)
        long long ans = min(dp[1][0], dp[1][1]);
        if (ans < inf)
            printf("%lld\n", ans);
        else
            printf("-1\n");
    }
    
    return 0;
}