代码

// 调试：各种u和v打错。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5, M = 2e5+5;
const ll INF = 1e15;
int n, m, u, v, w[N], x, y, dep[N], fa[N][20], 
	edgenum, Head[N], Next[M], vet[M]; ll dp[N][2], f[N][20][2][2], ans;
ll t0, t1, tu0, tu1, tv0, tv1;
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -w;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
		s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
inline void write1(ll x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write1(x / 10);
	putchar(x % 10 + '0');
}
inline void add(int u, int v) {
	Next[++edgenum] = Head[u];
	Head[u] = edgenum;
	vet[edgenum] = v;
}
void dfs1(int u, int F) {
	dep[u] = dep[F] + 1, fa[u][0] = F;
	for (int i=1; 1<<i<dep[u]; i++)
		fa[u][i] = fa[fa[u][i-1]][i-1];
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v == F) continue;
		dfs1(v, u);
		dp[u][0] += dp[v][1];
		dp[u][1] += min(dp[v][0], dp[v][1]);
	} dp[u][1] += w[u];
}
void dfs2(int u, int F) {
	f[u][0][0][0] = INF;
	f[u][0][0][1] = dp[F][1] - min(dp[u][0], dp[u][1]) + dp[u][0];
	f[u][0][1][0] = dp[F][0];
	f[u][0][1][1] = dp[F][1] - min(dp[u][0], dp[u][1]) + dp[u][1];
	for (int i=1; 1<<i<dep[u]; i++) {
		int _ = fa[u][i-1];
		f[u][i][0][0] = min(f[u][i-1][0][0] + f[_][i-1][0][0] - dp[_][0], 
							f[u][i-1][0][1] + f[_][i-1][1][0] - dp[_][1]);
		f[u][i][0][1] = min(f[u][i-1][0][0] + f[_][i-1][0][1] - dp[_][0], 
							f[u][i-1][0][1] + f[_][i-1][1][1] - dp[_][1]);
		f[u][i][1][0] = min(f[u][i-1][1][0] + f[_][i-1][0][0] - dp[_][0], 
							f[u][i-1][1][1] + f[_][i-1][1][0] - dp[_][1]);
		f[u][i][1][1] = min(f[u][i-1][1][0] + f[_][i-1][0][1] - dp[_][0], 
							f[u][i-1][1][1] + f[_][i-1][1][1] - dp[_][1]);
	}
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (v ^ F) dfs2(v, u);
	}
}
int main() {
	freopen ("defense.in", "r", stdin);
	freopen ("defense.out", "w", stdout);
	scanf ("%d%d%*s", &n, &m);
	for (int i=1; i<=n; i++)
		w[i] = read();
	for (int i=1; i<n; i++)
		u = read(), v = read(), 
		add(u, v), add(v, u);
	dfs1(1, 0), dfs2(1, 0);
	while (m--) {
		ans = INF;
		u = read(), x = read(), v = read(), y = read();
		if (dep[u] < dep[v]) swap(u, v), swap(x, y);
		ll u0 = INF, u1 = INF, v0 = INF, v1 = INF, k = dep[u] - dep[v];
		x ? u1 = dp[u][1] : u0 = dp[u][0], y ? v1 = dp[v][1] : v0 = dp[v][0];
		for (int i=17; ~i; i--)
			if (k & 1 << i) {
				t0 = u0, t1 = u1;
				u0 = min(t0 + f[u][i][0][0] - dp[u][0], t1 + f[u][i][1][0] - dp[u][1]);
				u1 = min(t0 + f[u][i][0][1] - dp[u][0], t1 + f[u][i][1][1] - dp[u][1]);
				u = fa[u][i];
			}
		if (u == v)
			y ? u0 = INF : u1 = INF;
		else {
			for (int i=17; ~i; i--)
				if (fa[u][i] ^ fa[v][i]) {
					tu0 = u0, tu1 = u1, tv0 = v0, tv1 = v1;
					u0 = min(tu0 + f[u][i][0][0] - dp[u][0], tu1 + f[u][i][1][0] - dp[u][1]);
					u1 = min(tu0 + f[u][i][0][1] - dp[u][0], tu1 + f[u][i][1][1] - dp[u][1]);
					v0 = min(tv0 + f[v][i][0][0] - dp[v][0], tv1 + f[v][i][1][0] - dp[v][1]);
					v1 = min(tv0 + f[v][i][0][1] - dp[v][0], tv1 + f[v][i][1][1] - dp[v][1]);
					u = fa[u][i], v = fa[v][i];
				}
			tu0 = u0, tu1 = u1, tv0 = v0, tv1 = v1;
			u0 = dp[fa[u][0]][0] - dp[u][1] - dp[v][1] + tu1 + tv1;
			u1 = dp[fa[u][0]][1] - min(dp[u][0], dp[u][1]) - min(dp[v][0], dp[v][1]) + min(tu0, tu1) + min(tv0, tv1);
			u = fa[u][0];
		}
		if (u == 1) ans = min(u0, u1);
		else {
			for (int i=17; ~i; i--)
				if (fa[u][i] && fa[u][i] != 1) {
					t0 = u0, t1 = u1;
					u0 = min(t0 + f[u][i][0][0] - dp[u][0], t1 + f[u][i][1][0] - dp[u][1]);
					u1 = min(t0 + f[u][i][0][1] - dp[u][0], t1 + f[u][i][1][1] - dp[u][1]);
					u = fa[u][i];
				}
			t0 = u0, t1 = u1;
			u0 = dp[1][0] - dp[u][1] + t1;
			u1 = dp[1][1] - min(dp[u][0], dp[u][1]) + min(t0, t1);
			ans = min(u0, u1);
		}
		write1(ans >= INF - 1e10 ? -1 : ans), putchar('\n');
	} return 0;
}

评测结果