代码

//waz
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

#define int long long

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int N = 2e5 + 10;

const long long oo = 1e12;

struct item
{
	long long res[2][2];
	bool ok;
	friend item operator + (item a, item b)
	{
		item c;
		if (!a.ok) return b;
		if (!b.ok) return a;
		c.res[0][0] = min(a.res[0][1] + b.res[0][0], min(a.res[0][0] + b.res[1][0], a.res[0][1] + b.res[1][0]));
		c.res[0][1] = min(a.res[0][1] + b.res[0][1], min(a.res[0][0] + b.res[1][1], a.res[0][1] + b.res[1][1]));
		c.res[1][0] = min(a.res[1][1] + b.res[0][0], min(a.res[1][0] + b.res[1][0], a.res[1][1] + b.res[1][0]));
		c.res[1][1] = min(a.res[1][1] + b.res[0][1], min(a.res[1][0] + b.res[1][1], a.res[1][1] + b.res[1][1]));
		c.ok = 1;
		return c;
	}
	void init(long long *t)
	{
		res[0][0] = t[0];
		res[1][1] = t[1];
		res[0][1] = res[1][0] = oo;
		ok = 1;
	}
	void rev() { swap(res[0][1], res[1][0]); } 
} dp[N], ff[N], t[N][20];

struct edge
{
	int to;
	edge *next;
} e[N << 1], *et = e, *last[N];

void add(int u, int v)
{
	*++et = (edge) {v, last[u]}, last[u] = et;
	*++et = (edge) {u, last[v]}, last[v] = et;
}

long long f[N][2];

int p[N], fa[N], pa[N][20], dep[N];

void dfs(int u)
{
	f[u][1] = p[u], f[u][0] = 0;
	dep[u] = dep[fa[u]] + 1;
	for (edge *it = last[u]; it; it = it -> next)
	{
		int v = it -> to;
		if (fa[u] == v) continue;
		fa[v] = u;
		dfs(v);
		f[u][0] += f[v][1];
		f[u][1] += min(f[v][0], f[v][1]);
	}
	for (edge *it = last[u]; it; it = it -> next)
	{
		int v = it -> to;
		if (fa[u] == v) continue;
		long long t[2];
		t[0] = f[u][0] - f[v][1];
		t[1] = f[u][1] - min(f[v][0], f[v][1]);
		dp[v].init(t);
	}
}

void dfs2(int u)
{
	ff[u].init(f[u]);
	t[u][0] = dp[u];
	pa[u][0] = fa[u];
	for (int i = 1; i <= 18; ++i)
	{
		pa[u][i] = pa[pa[u][i - 1]][i - 1];
		t[u][i] = t[u][i - 1] + t[pa[u][i - 1]][i - 1];
	}
	for (edge *it = last[u]; it; it = it -> next)
	{
		int v = it -> to;
		if (fa[u] == v) continue;
		dfs2(v);
	}
}

int jump(int u, int k)
{
	for (int i = 18; ~i; --i)
		if (k & (1 << i)) u = pa[u][i];
	return u;
}

int query_lca(int u, int v, int &U, int &V)
{
	u = jump(u, dep[u] - dep[v]);
	if (u == v) return u;
	for (int i = 18; ~i; --i)
		if (pa[u][i] != pa[v][i]) u = pa[u][i], v = pa[v][i];
	U = u, V = v;
	return fa[u];
}

item query_jump(int u, int k)
{
	item ret;
	ret.ok = 0;
	for (int i = 18; ~i; --i)
		if (k & (1 << i)) ret = ret + t[u][i], u = pa[u][i];
	return ret;
}

long long query(int u, bool uu, int v, bool vv)
{
	if (dep[u] < dep[v]) swap(u, v), swap(uu, vv);
	int U, V;
	int lca = query_lca(u, v, U, V);
	if (v == lca)
	{
		item a = query_jump(v, dep[v] - 1);
		item b = query_jump(u, dep[u] - dep[v] - 1);
		U = jump(u, dep[u] - dep[v] - 1);
		long long g[2];
		g[0] = f[v][0] - f[U][1];
		g[1] = f[v][1] - min(f[U][1], f[U][0]);
		//cerr << "debug = " << b.res[1][1] << endl;
		item xx;
		xx.init(g);
		a = xx + a;
		g[0] = min(a.res[0][1], a.res[0][0]);
		g[1] = min(a.res[1][0], a.res[1][1]);
		a.init(g);
		return (ff[u] + b + a).res[uu][vv];
	}
	item a = query_jump(lca, dep[lca] - 1);
	item b = query_jump(u, dep[u] - dep[lca] - 1);
	item c = query_jump(v, dep[v] - dep[lca] - 1);
	c.rev();
	long long g[2];
	g[0] = f[lca][0] - f[U][1] - f[V][1];
	g[1] = f[lca][1] - min(f[U][1], f[U][0]) - min(f[V][1], f[V][0]);
	item xx;
	xx.init(g);
	a = xx + a;
	g[0] = min(a.res[0][1], a.res[0][0]);
	g[1] = min(a.res[1][0], a.res[1][1]);
	a.init(g);
	item d = ff[v];
	d.rev();
	return (ff[u] + b + a + c + d).res[uu][vv];
}

int n, m;

main()
{
	//freopen("1.in", "r", stdin);
	gii(n, m);
	static char type[233];
	scanf("%s", type);
	for (int i = 1; i <= n; ++i) gi(p[i]);
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		gii(u, v);
		add(u, v);
	}
	dfs(1);
	dfs2(1);
	while (m--)
	{
		int a, x, b, y;
		gii(a, x);
		gii(b, y);
		long long res = query(a, x, b, y);
		if (res >= oo) puts("-1");
		else printf("%lld\n", res);
	}
	return 0;
}

评测结果