题目传送门

　　传送门

/**

 * loj

 * Problem#2955

 * Accepted

 * Time: 2653ms

 * Memory: 25616k

 */

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

const int N = 1e5 + 5;

#define ll long long

template <typename T>

T smin(T a, T b) {

	return min(a, b);

}

template <typename T, typename ...Q>

T smin(T a, const Q &...args) {

	return min(a, smin(args...));

}

const ll llf = 1e12;

typedef class Data {

	public:

		ll a[2][2];

		Data() {	}

		Data(ll x) {

			a[0][0] = llf, a[0][1] = 0;

			a[1][0] = x, a[1][1] = x;

		}

		Data(ll x, ll y, ll z, ll w) {

			a[0][0] = x, a[0][1] = y;

			a[1][0] = z, a[1][1] = w;

		}

		Data get() {

			ll g = min(a[0][0], a[0][1]);

			ll f = min(a[1][0], a[1][1]);

			g = min(g, f);

			return Data(f, f, g, g);

		}

		ll* operator [] (int p) {

			return a[p];

		}

		friend Data operator * (Data a, Data b) {

			Data rt;

			rt[0][0] = min(a[0][0] + b[0][0], a[0][1] + b[1][0]);

			rt[0][1] = min(a[0][0] + b[0][1], a[0][1] + b[1][1]);

			rt[1][0] = min(a[1][0] + b[0][0], a[1][1] + b[1][0]);

			rt[1][1] = min(a[1][0] + b[0][1], a[1][1] + b[1][1]);

			return rt;

		}

		friend Data operator + (Data a, Data b) {

			Data rt;

			rt[0][0] = a[0][0] + b[0][0];

			rt[0][1] = a[0][1] + b[0][1];

			rt[1][0] = a[1][0] + b[1][0];

			rt[1][1] = a[1][1] + b[1][1];

			return rt;

		}

		friend Data operator - (Data a, Data b) {

			Data rt;

			rt[0][0] = a[0][0] - b[0][0];

			rt[0][1] = a[0][1] - b[0][1];

			rt[1][0] = a[1][0] - b[1][0];

			rt[1][1] = a[1][1] - b[1][1];

			return rt;

		}

		ll get_ans() {

			ll rt = smin(a[0][0], a[0][1], a[1][0], a[1][1]);

			return (rt >= llf) ? (-1) : (rt);

		}

} Data;

typedef class SegTreeNode {

	public:

		Data d;

		SegTreeNode *fa;

		SegTreeNode *l, *r;

		void push_up() {

			d = l->d * r->d;

		}

} SegTreeNode;

typedef class Chain {

	public:

		SegTreeNode *st;

		int len, top;

		Chain() {	}

		Chain(int top);

		void update(int, Data, Data);

} Chain;

SegTreeNode pool[N << 1];

SegTreeNode *_top = pool;

int S[N];

Data dat[N];

int tp;

Chain *ch[N];

SegTreeNode *tr[N];

void build(SegTreeNode*& p, int l, int r) {

	p = _top++;

	if (l == r) {

		p->d = dat[S[l]];

		tr[S[l]] = p;

		return;

	}

	int mid = (l + r) >> 1;

	build(p->l, l, mid);

	build(p->r, mid + 1, r);

	p->push_up();

	p->l->fa = p;

	p->r->fa = p;

}

Chain::Chain(int top) : st(_top), len(tp), top(top) {

	reverse(S + 1, S + tp + 1);

	build(st, 1, len);

	for (int i = 1; i <= len; i++) {

		ch[S[i]] = this;

	}

	if (top) {

		dat[top] = dat[top] + st->d.get();

	}

}

void Chain::update(int x, Data old_d, Data new_d) {

	Data nold_d = st->d.get();

	tr[x]->d = tr[x]->d - old_d + new_d;

	for (SegTreeNode *p = tr[x]->fa; p; p = p->fa)

		p->push_up();

	if (top) {

		ch[top]->update(top, nold_d, st->d.get());

	}

}

int n, m;

int p[N];

int sz[N], zson[N];

vector<int> G[N];

void dfs1(int p, int fa) {

	int mx = 0, &id = zson[p];

	sz[p] = 1;

	for (auto e : G[p]) {

		if (e ^ fa) {

			dfs1(e, p);

			sz[p] += sz[e];

			if (mx < sz[e]) {

				mx = sz[e];

				id = e;

			}

		}

	}

}

void dfs2(int p, int fa) {

	if (zson[p]) {

		for (auto e : G[p]) {

			if ((e ^ fa) && (e ^ zson[p])) {

				dfs2(e, p);

				new Chain(p);

			}

		}

		dfs2(zson[p], p);

	} else {

		tp = 0;

	}

	S[++tp] = p;

}

int main() {

	freopen("defense.in", "r", stdin);

	freopen("defense.out", "w", stdout);

	scanf("%d%d%*s", &n, &m);

	for (int i = 1, x; i <= n; i++) {

		scanf("%d", &x);

		dat[i] = x;

		p[i] = x;

	}

	for (int i = 1, u, v; i < n; i++) {

		scanf("%d%d", &u, &v);

		G[u].push_back(v);

		G[v].push_back(u);

	}

	dfs1(1, 0);

	dfs2(1, 0);

	new Chain(0);

	int a, x, b, y;

	while (m--) {

		scanf("%d%d%d%d", &a, &x, &b, &y);

		Data olda = p[a], oldb = p[b];

		Data na = Data(llf * (1 - x)), nb = Data(llf * (1 - y));

		ch[a]->update(a, olda, na);

		ch[b]->update(b, oldb, nb);

		ll ans = ch[1]->st->d.get_ans() + olda[1][0] * x + oldb[1][0] * y;

		ch[a]->update(a, na, olda);

		ch[b]->update(b, nb, oldb);

		printf("%lld\n", ans);

	}

	return 0;

}