代码

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e5 + 5;
constexpr i64 INF = (1ll << 60), INF2 = INF / 2;

void chmax(int &x, int y) { if (y > x) x = y; }
void chmin(int &x, int y) { if (y < x) x = y; }

struct Matrix {
	static constexpr int N = 2; int n, m; i64 a[N][N];
	void init(int _n, int _m) { 
		n = _n; m = _m;
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] = -INF; 
	}
	Matrix(int n = 0, int m = 0) { init(n, m); }
	Matrix operator * (const Matrix &rhs) const {
		assert(m == rhs.n); Matrix ret(n, rhs.m);
		ret.a[0][0] = std::max(a[0][0] + rhs.a[0][0], a[0][1] + rhs.a[1][0]);
		ret.a[0][1] = std::max(a[0][0] + rhs.a[0][1], a[0][1] + rhs.a[1][1]);
		ret.a[1][0] = std::max(a[1][0] + rhs.a[0][0], a[1][1] + rhs.a[1][0]);
		ret.a[1][1] = std::max(a[1][0] + rhs.a[0][1], a[1][1] + rhs.a[1][1]);
		// for (int i = 0; i < n; i++) for (int j = 0; j < rhs.m; j++) for (int k = 0; k < m; k++) chmax(ret.a[i][j], a[i][k] + rhs.a[k][j]);
		return ret;
	}
	void print() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) std::cout << a[i][j] << " \n"[j == m - 1]; }
} I;

Matrix gen(i64 f0, i64 f1) {
	Matrix ret(2, 2);
	ret.a[0][0] = ret.a[0][1] = f0;
	ret.a[1][0] = f1; ret.a[1][1] = -INF;
	return ret;
}

int n, m, timer;
int dfn[N], rnk[N], siz[N], dep[N], fa[N], son[N], top[N], bot[N];
i64 all, a[N], f[N][2], g[N][2];
std::string o;
std::vector<int> G[N];

struct SegTree {
	static constexpr int N = 1e5 + 5;
	Matrix data[N << 2];

	#define ls(u) (u << 1)
	#define rs(u) (u << 1 | 1)

	void build(int u, int l, int r) {
		data[u].init(2, 2);
		if (l == r) return data[u] = gen(g[rnk[l]][0], g[rnk[l]][1]), void();
		int mid = (l + r) >> 1;
		build(ls(u), l, mid); build(rs(u), mid + 1, r);
		data[u] = data[ls(u)] * data[rs(u)];
	}

	void modify(int u, int l, int r, int pos, Matrix val) {
		if (l == r) return data[u] = val, void();
		int mid = (l + r) >> 1;
		if (pos <= mid) modify(ls(u), l, mid, pos, val);
		if (pos > mid)  modify(rs(u), mid + 1, r, pos, val);
		data[u] = data[ls(u)] * data[rs(u)];
	}

	Matrix query(int u, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) return data[u];
		int mid = (l + r) >> 1; Matrix ret = I;
		if (ql <= mid) ret = ret * query(ls(u), l, mid, ql, qr);
		if (qr > mid)  ret = ret * query(rs(u), mid + 1, r, ql, qr);
		return ret;
	}
} tree;

void dfs1(int u, int fa) {
	siz[u] = 1; ::fa[u] = fa; dep[u] = dep[fa] + 1;
	f[u][0] = 0, f[u][1] = a[u];
	for (auto v : G[u]) if (v != fa) {
		dfs1(v, u); siz[u] += siz[v];
		f[u][0] += std::max(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
		if (siz[v] > siz[son[u]]) son[u] = v;
	}
}

void dfs2(int u, int tp) {
	bot[top[u] = tp] = u; rnk[dfn[u] = ++timer] = u;
	g[u][0] = 0, g[u][1] = a[u];
	if (son[u]) dfs2(son[u], tp);
	for (auto v : G[u]) if (v != fa[u] && v != son[u]) {
		g[u][0] += std::max(f[v][0], f[v][1]);
		g[u][1] += f[v][0];
		dfs2(v, v);
	}
}

void update(int x, i64 y) {
	g[x][1] += y - a[x]; a[x] = y; Matrix lst, now;
	lst = tree.query(1, 1, n, dfn[top[x]], dfn[bot[top[x]]]);
	tree.modify(1, 1, n, dfn[x], gen(g[x][0], g[x][1]));
	while (top[x] != 1) {
		now = tree.query(1, 1, n, dfn[top[x]], dfn[bot[top[x]]]);
		x = fa[top[x]];
		g[x][0] += std::max(now.a[0][0], now.a[1][0]) - std::max(lst.a[0][0], lst.a[1][0]);
		g[x][1] += now.a[0][0] - lst.a[0][0];
		lst = tree.query(1, 1, n, dfn[top[x]], dfn[bot[top[x]]]);
		tree.modify(1, 1, n, dfn[x], gen(g[x][0], g[x][1]));
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	I.init(2, 2); I.a[0][0] = I.a[1][1] = 0;

	std::cin >> n >> m >> o;
	for (int i = 1; i <= n; i++) std::cin >> a[i], all += a[i];
	for (int i = 1; i < n; i++) {
		int u, v; std::cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0); dfs2(1, 1); tree.build(1, 1, n);
	while (m--) {
        int u, x, v, y; std::cin >> u >> x >> v >> y;
        int ou = a[u], ov = a[v];
        if (!x && !y && (fa[u] == v || fa[v] == u)) {
            std::cout << "-1" << "\n";
            continue;
        }
        update(u, (x ? -INF2 : INF2)), update(v, (y ? -INF2 : INF2));
		Matrix res = tree.query(1, 1, n, 1, dfn[bot[1]]);
		std::cout << all - (std::max(res.a[0][0], res.a[1][0]) - (x ? 0 : INF2 - ou) - (y ? 0 : INF2 - ov)) << "\n";
        update(u, ou), update(v, ov);
	}

	return 0;
}

评测结果