代码

#include<bits/stdc++.h>
#define inf (long long)1e12
#define add(u, v) to[++tot] = v, nxt[tot] = hd[u], hd[u] = tot
#define LL long long
using namespace std;
const int N = 100000 + 5;

int n, m;
int to[N << 1], nxt[N << 1], hd[N], tot;
LL p[N], dep[N], fa[N][19], dp[N][2], f[N][19][2][2];
string type;

void dfs(int u) {
	dp[u][1] = p[u];
	for (int i = hd[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v == fa[u][0]) continue;
		dep[v] = dep[u] + 1; fa[v][0] = u;
		dfs(v);
		dp[u][1] += min(dp[v][0], dp[v][1]);
		dp[u][0] += dp[v][1]; 
	}
}

void init(void) {
	dep[1] = 1; dfs(1);
	for (int i = 1; i <= n; i++) {
		f[i][0][0][0] = inf;
		f[i][0][1][0] = dp[fa[i][0]][0] - dp[i][1];
		f[i][0][1][1] = f[i][0][0][1] = dp[fa[i][0]][1] - min(dp[i][0], dp[i][1]);
	}
	for (int k = 1; k <= 18; k++) {
		for (int i = 1; i <= n; i++) {
			int F = fa[i][k - 1];
			fa[i][k] = fa[F][k - 1];
			for (int x = 0; x < 2; x++) {
				for (int y = 0; y < 2; y++) {
					f[i][k][x][y] = min(f[i][k - 1][x][0] + f[F][k - 1][0][y], f[i][k - 1][x][1] + f[F][k - 1][1][y]);
				}
			}
		}
	}
}

inline void Work(int u, int x, int v, int y) {
	if(dep[u] < dep[v]) swap(u, v), swap(x, y);
	LL a[2] = {inf, inf}, b[2] = {inf, inf}, res[2] = {inf, inf}, tmp[2]; int lca;
	a[x] = dp[u][x], b[y] = dp[v][y];
	for(int k = 18; k >= 0; k--) if (dep[fa[u][k]] >= dep[v]){
		for(int i = 0; i < 2; i++) tmp[i] = a[i];
		for(int i = 0; i < 2; i++) a[i] = min(tmp[0] + f[u][k][0][i], tmp[1] + f[u][k][1][i]); 
		u = fa[u][k];
	}
	if(u == v) {
		lca = u;
		res[y] = a[y];
	}
	else {
		for(int k = 18; k >= 0; k--) if (fa[u][k] != fa[v][k]) {
			for(int i = 0; i < 2; i++) tmp[i] = a[i];
			for(int i = 0; i < 2; i++) a[i] = min(tmp[0] + f[u][k][0][i], tmp[1] + f[u][k][1][i]);
			for(int i = 0; i < 2; i++) tmp[i] = b[i];
			for(int i = 0; i < 2; i++) b[i] = min(tmp[0] + f[v][k][0][i], tmp[1] + f[v][k][1][i]);
			u = fa[u][k], v = fa[v][k];
		}
		lca = fa[u][0];
		res[0] = dp[lca][0] - dp[u][1] - dp[v][1] + a[1] + b[1];
		res[1] = dp[lca][1] - min(dp[u][0], dp[u][1]) - min(dp[v][0], dp[v][1]) + min(a[0], a[1]) + min(b[0], b[1]); 
	}
	for(int k = 18; k >= 0; --k) if (dep[fa[lca][k]]) {
		for(int i = 0; i < 2; ++i) tmp[i] = res[i];
		for(int i = 0; i < 2; ++i) res[i] = min(tmp[0] + f[lca][k][0][i], tmp[1] + f[lca][k][1][i]);
		lca = fa[lca][k];
	}
	LL ans = min(res[0], res[1]);
	printf("%lld\n", ans < inf ? ans : -1);
}

int main() {
	cin >> n >> m >> type;
	for (int i = 1; i <= n; i++) scanf("%lld", &p[i]);
	for (int i = 1; i <= n - 1; i++) {
		int u, v; scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	init();
	while (m--) {
		int u, x, v, y;
		scanf("%d%d%d%d", &u, &x, &v, &y);
		Work(u, x, v, y);
	}
	return 0;
}

评测结果