代码

#include <cstdio>
#include <algorithm>
//#pragma GCC optimize("O3","Ofast","-ffast-math","-funroll-loops")

namespace fastio
{
	const int MAXBUF = 1 << 23;
	char buf[MAXBUF], *p1 = buf, *p2 = buf;
	char pbuf[MAXBUF], *pp = pbuf;
	inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), p1 == p2 ? EOF : *p1++; }
	inline void putc(char c) { (pp == pbuf + MAXBUF) && (fwrite(pbuf, 1, MAXBUF, stdout), pp = pbuf), *pp++ = c; }
	inline void print_final() { fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf; }
}
using fastio::getc;
using fastio::putc;
using fastio::print_final;
template <class Tp> inline Tp& read(Tp& x)
{
	bool sign = 0;
	char c = getc();
	for (; !('0' <= c && c <= '9'); c = getc()) sign |= (c == '-');
	for (x = 0; '0' <= c && c <= '9'; c = getc()) x = x * 10 + (c ^ 48);
	return sign ? (x = -x) : x;
}
template <class Tp> inline void write(Tp x)
{
	if (x < 0) putc('-'), x = -x;
	if (x > 9) write(x / 10);
	putc((x % 10) ^ 48);
}
#include <cctype>
inline void getstr(char *s)
{
	char c = getc();
	for (; isspace(c); c = getc());
	for (; c != EOF && !isspace(c); c = getc()) *s++ = c;
	*s = '\0';
}
inline void putstr(char *s)
{
	for (; *s != '\0'; s++) putc(*s);
}

const int maxn = 1e5 + 10;

const long long inf = 1LL << 60;

struct matrix
{
	long long a[4];
	matrix(long long a0 = inf, long long a1 = inf, long long a2 = inf, long long a3 = inf)
	{ a[0] = a0, a[1] = a1, a[2] = a2, a[3] = a3; }
	matrix operator * (const matrix &t) const
	{
		matrix ans;
		ans.a[0] = std::min(a[0] + t.a[0], a[1] + t.a[2]);
		ans.a[1] = std::min(a[0] + t.a[1], a[1] + t.a[3]);
		ans.a[2] = std::min(a[2] + t.a[0], a[3] + t.a[2]);
		ans.a[3] = std::min(a[2] + t.a[1], a[3] + t.a[3]);
		return ans;
	}
};

struct graph
{
	int cnt = 0, st[maxn * 2], to[maxn * 2], next[maxn * 2], last[maxn];
	void add(int x, int y) { cnt++, st[cnt] = x, to[cnt] = y, next[cnt] = last[x], last[x] = cnt; }
}
G;

int fa[maxn], depth[maxn], size[maxn], son[maxn];

void dfs1(int u, int fath)
{
	fa[u] = fath, depth[u] = depth[fa[u]] + 1, size[u] = 1, son[u] = 0;
	for (int j = G.last[u]; j != 0; j = G.next[j])
	{
		int v = G.to[j];
		if (v == fa[u]) continue;
		dfs1(v, u);
		size[u] += size[v];
		if (son[u] == 0 || size[v] > size[son[u]]) son[u] = v;
	}
}

int dfx = 0, dfn[maxn], top[maxn], end[maxn];

void dfs2(int u, int low)
{
	dfn[u] = ++dfx, top[u] = low;
	if (son[u] != 0) dfs2(son[u], low), end[u] = end[son[u]];
	else end[u] = u;
	for (int j = G.last[u]; j != 0; j = G.next[j])
	{
		int v = G.to[j];
		if (v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}

struct segmenttree
{
	struct node
	{
		int l, r;
		matrix m;
	}
	T[maxn * 4];
	
	void build(int l, int r, int p = 1)
	{
		T[p].l = l, T[p].r = r;
		if (l != r) build(l, (l + r) / 2, 2 * p), build((l + r) / 2 + 1, r, 2 * p + 1);
	}
	
	void modify(int k, const matrix &m, int p = 1)
	{
		if (T[p].l == T[p].r) T[p].m = m;
		else if (k <= T[2 * p].r) modify(k, m, 2 * p), T[p].m = T[2 * p + 1].m * T[2 * p].m;
		else modify(k, m, 2 * p + 1), T[p].m = T[2 * p + 1].m * T[2 * p].m;
	}
	
	matrix query(int l, int r, int p = 1)
	{
		if (l <= T[p].l && T[p].r <= r) return T[p].m;
		else if (r <= T[2 * p].r) return query(l, r, 2 * p);
		else if (l >= T[2 * p + 1].l) return query(l, r, 2 * p + 1);
		else return query(l, r, 2 * p + 1) * query(l, r, 2 * p);
	}
}
T;

std::pair<long long, long long> query(int u)
{
	matrix m(0, 0);
	m = m * T.query(dfn[u], dfn[end[u]]);
	return {m.a[0], m.a[1]};
}

void modify(int u, const matrix &k)
{
	if (u == 0) return;
	std::pair<long long, long long> _f = query(top[u]);
	T.modify(dfn[u], k);
	std::pair<long long, long long> f = query(top[u]);
	matrix m = T.query(dfn[fa[top[u]]], dfn[fa[top[u]]]);
	m.a[1] = m.a[3] = m.a[1] + std::min(f.first, f.second) - std::min(_f.first, _f.second);
	m.a[2] = m.a[2] + f.second - _f.second;
	modify(fa[top[u]], m);
}

long long a[maxn];
long long f[maxn][2];
long long g[maxn][2];

void dp(int u)
{
	f[u][0] = 0, f[u][1] = a[u];
	g[u][0] = 0, g[u][1] = a[u];
	for (int j = G.last[u]; j != 0; j = G.next[j])
	{
		int v = G.to[j];
		if (v == fa[u]) continue;
		dp(v);
		f[u][0] += f[v][1];
		f[u][1] += std::min(f[v][0], f[v][1]);
		if (v == son[u]) continue;
		g[u][0] += f[v][1];
		g[u][1] += std::min(f[v][0], f[v][1]);
	}
}

void change(int u, long long k)
{
	matrix m = T.query(dfn[u], dfn[u]);
	m.a[1] = m.a[3] = m.a[1] + k - a[u];
	a[u] = k;
	modify(u, m);
}

int main()
{
//	freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
	int n, m;
	read(n), read(m);
	char type[3];
	getstr(type);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i < n; i++)
	{
		int u, v;
		read(u), read(v);
		G.add(u, v), G.add(v, u);
	}
	dfs1(1, 0), dfs2(1, 1), dp(1);
	T.build(1, n);
	for (int i = 1; i <= n; i++)
	{
		matrix m = {inf, g[i][1], g[i][0], g[i][1]};
		T.modify(dfn[i], m);
	}
	while (m--)
	{
		int u, x, v, y;
		read(u), read(x), read(v), read(y);
		if (x == 0 && y == 0 && (fa[u] == v || fa[v] == u)) { write(-1), putc('\n'); continue; }
		long long _u = a[u], _v = a[v];
		change(u, x == 0 ? 2 * inf : -inf);
		change(v, y == 0 ? 2 * inf : -inf);
		std::pair<long long, long long> ans = query(1);
		write(std::min(ans.first, ans.second) + (x == 1 ? inf + _u : 0) + (y == 1 ? inf + _v : 0)), putc('\n');
		change(u, _u), change(v, _v);
	}
	return print_final(), 0;
}

评测结果