代码

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

typedef long long ll;
const int maxn = 100010;
int n, m, fa[maxn], ch[maxn][2];
ll p[maxn], dp[maxn][2];
vector<int> G[maxn];
struct mat { ll a, b, c, d; mat() { a = b = c = d = 1e18; } } f[maxn], g[maxn];

bool get(int v) { return v == ch[fa[v]][1]; }
bool is_root(int v) { return ch[fa[v]][0] ^ v && ch[fa[v]][1] ^ v; }

mat operator * (mat &A, mat &B) {
	mat C;
	C.a = min(A.a + B.a, A.b + B.c), C.b = min(A.a + B.b, A.b + B.d);
	C.c = min(A.c + B.a, A.d + B.c), C.d = min(A.c + B.b, A.d + B.d);
	return C;
}

void dfs(int v) {
	dp[v][1] = p[v];
	for (int i = 0, u; i < G[v].size(); i++) {
		if ((u = G[v][i]) ^ fa[v]) {
			fa[u] = v, dfs(u);
			dp[v][0] += dp[u][1], dp[v][1] += min(dp[u][0], dp[u][1]);
		}
	}
	g[v].b = dp[v][0], g[v].c = dp[v][1];
}

void maintain(int v) {
	g[v].d = g[v].c, f[v] = g[v];
	if (ch[v][0]) f[v] = f[ch[v][0]] * f[v];
	if (ch[v][1]) f[v] = f[v] * f[ch[v][1]];
}

void rotate(int v) {
	int old = fa[v], oldf = fa[old], chk = get(v);
	if (!is_root(old)) ch[oldf][get(old)] = v;
	ch[old][chk] = ch[v][chk ^ 1], fa[ch[old][chk]] = old;
	ch[v][chk ^ 1] = old, fa[old] = v, fa[v] = oldf;
	maintain(old), maintain(v);
}

void splay(int v) {
	for (int f = fa[v]; !is_root(v); rotate(v), f = fa[v]) {
		if (!is_root(f)) rotate(get(v) ^ get(f) ? v : f);
	}
}

void access(int v) {
	for (int u = 0, t; v; v = fa[u = v]) {
		splay(v);
		if (t = ch[v][1]) g[v].b += f[t].d, g[v].c += min(f[t].b, f[t].d);
		if (ch[v][1] = u) g[v].b -= f[u].d, g[v].c -= min(f[u].b, f[u].d);
		maintain(v);
	}
}

void upd(int v, ll w) {
	access(v), splay(v), g[v].c += w - p[v];
	p[v] = w, maintain(v);
}

int main() {
	scanf("%d %d %*s", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &p[i]);
	}
	for (int i = 1, u, v; i < n; i++) {
		scanf("%d %d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	dfs(1);
	for (int i = 1, a, b, x, y; i <= m; i++) {
		scanf("%d %d %d %d", &a, &x, &b, &y);
		ll olda = p[a], oldb = p[b], ans = 0;
		if (x) upd(a, 0), ans += olda; else upd(a, 2e15);
		if (y) upd(b, 0), ans += oldb; else upd(b, 2e15);
		splay(1), ans += min(f[1].b, f[1].d);
		printf("%lld\n", ans > 1e15 ? -1 : ans);
		upd(a, olda), upd(b, oldb);
	}
	return 0;
}

评测结果