代码

#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>

const size_t _IO_size = 1 << 21 | 1;
char iBuf[_IO_size], *iS, *iE;
inline char getc() { return iS == iE ? iE = iBuf + fread(iS = iBuf, 1, _IO_size, stdin), iS == iE ? EOF : *iS++ : *iS++; }
template <typename T>
void readi(T &x)
{
	char c;
	for (c = getc(); !isdigit(c); c = getc())
		;
	x = c ^ '0';
	for (c = getc(); isdigit(c); c = getc())
		(x *= 10) += c ^ '0';
}

typedef long long ll;
const size_t maxN = 100005;
const ll INF = 1000000000000000LL;

int N, M, Type;
ll P[maxN];
std::vector<int> G[maxN];

int Fa[maxN], Size[maxN], Son[maxN], Top[maxN], End[maxN], Tid[maxN], rTid[maxN], Index;
ll F[maxN][2];

void DFS1(int i)
{
	Size[i] = 1;
	F[i][0] = 0, F[i][1] = P[i];
	for (auto to : G[i])
		if (to != Fa[i])
		{
			Fa[to] = i;
			DFS1(to);
			Size[i] += Size[to];
			if (Size[to] > Size[Son[i]])
				Son[i] = to;
			F[i][0] += F[to][1];
			F[i][1] += std::min(F[to][0], F[to][1]);
		}
}

void DFS2(int i)
{
	rTid[Tid[i] = ++Index] = i;
	End[Top[i]] = i;
	if (Son[i])
		Top[Son[i]] = Top[i], DFS2(Son[i]);
	for (auto to : G[i])
		if (to != Fa[i] && to != Son[i])
			Top[to] = to, DFS2(to);
}

struct matrix_t
{
	ll __v[2][2];
	matrix_t() {}
	matrix_t(ll f0, ll f1)
	{
		__v[0][0] = 0x3F3F3F3F3F3F3F3FLL;
		__v[0][1] = f0;
		__v[1][0] = f1;
		__v[1][1] = f1;
	}
	inline ll *operator[](int x)
	{
		return __v[x];
	}
	inline const ll *operator[](int x) const
	{
		return __v[x];
	}
} Seg[1 << 18 | 1];

matrix_t operator*(const matrix_t &a, const matrix_t &b)
{
	matrix_t res;
	for (int i = 0; i != 2; ++i)
		for (int j = 0; j != 2; ++j)
			res[i][j] = std::min(a[i][0] + b[0][j], a[i][1] + b[1][j]);
	return res;
}

namespace zkw
{
int L;
void build(int n)
{
	for (L = 1; L <= n + 1; L <<= 1)
		;
	for (int i = 1; i <= n; ++i)
	{
		int u = rTid[i];
		Seg[i + L] = matrix_t(F[u][0] - F[Son[u]][1], F[u][1] - std::min(F[Son[u]][0], F[Son[u]][1]));
	}
	for (int i = L - 1; i; --i)
		Seg[i] = Seg[i << 1] * Seg[i << 1 | 1];
}
void modify(int pos, ll d0, ll d1)
{
	int i = pos + L;
	Seg[i][0][1] += d0;
	Seg[i][1][0] += d1;
	Seg[i][1][1] += d1;
	for (i >>= 1; i; i >>= 1)
		Seg[i] = Seg[i << 1] * Seg[i << 1 | 1];
}
matrix_t query(int tl, int tr)
{
	matrix_t l, r;
	bool visl = false, visr = false;
	for (tl = tl - 1 + L, tr = tr + 1 + L; (tl ^ tr) != 1; tl >>= 1, tr >>= 1)
	{
		if (~tl & 1)
		{
			if (!visl)
				visl = true, l = Seg[tl ^ 1];
			else
				l = l * Seg[tl ^ 1];
		}
		if (tr & 1)
		{
			if (!visr)
				visr = true, r = Seg[tr ^ 1];
			else
				r = Seg[tr ^ 1] * r;
		}
	}
	return !visl ? r : !visr ? l : l * r;
}
} // namespace zkw

inline matrix_t query(int u)
{
	return zkw::query(Tid[u], Tid[End[Top[u]]]);
}

void erase(int u)
{
	if (u == 1)
		return;
	erase(Top[Fa[u]]);
	auto t = query(u);
	zkw::modify(Tid[Fa[u]], -std::min(t[1][0], t[1][1]), -std::min({t[0][0], t[0][1], t[1][0], t[1][1]}));
}

void modify(int u, ll v)
{
	erase(Top[u]);
	zkw::modify(Tid[u], 0, v);
	P[u] += v;
	u = Top[u];
	while (u != 1)
	{
		auto t = query(u);
		zkw::modify(Tid[Fa[u]], std::min(t[1][0], t[1][1]), std::min({t[0][0], t[0][1], t[1][0], t[1][1]}));
		u = Top[Fa[u]];
	}
}

int main()
{
	readi(N), readi(M), readi(Type);
	for (int i = 1; i <= N; ++i)
		readi(P[i]);
	for (int u, v, i = 1; i != N; ++i)
	{
		readi(u), readi(v);
		G[u].push_back(v), G[v].push_back(u);
	}

	DFS1(1);
	Top[1] = 1, DFS2(1);

	zkw::build(N);

	for (int a, x, b, y; M--;)
	{
		readi(a), readi(x), readi(b), readi(y);
		modify(a, x == 0 ? INF : -INF);
		modify(b, y == 0 ? INF : -INF);
		auto t = query(1);
		ll ans = std::min({t[0][0], t[0][1], t[1][0], t[1][1]}) + INF * (x + y);
		if (ans >= INF)
			puts("-1");
		else
			printf("%lld\n", ans);
		modify(a, x == 0 ? -INF : INF);
		modify(b, y == 0 ? -INF : INF);
	}

	return 0;
}

评测结果