C++14(g++5.4) 解法, 执行用时: 823ms, 内存消耗: 12892K, 提交时间: 2019-05-17 22:11:37

#include <bits/stdc++.h>
using namespace std;

const size_t maxn = 1 << 17;
size_t father[maxn], fa[maxn];
vector<size_t> son[maxn];
int64_t w[maxn], c[maxn], a[maxn], b[maxn];

void find(size_t u, int64_t x) {
	if (!u) {
		b[0] -= x;
		return;
	}
	int64_t mi = min(x, b[fa[u]]);
	b[fa[u]] -= mi;
	x -= mi;
	if (x) {
		find(father[fa[u]], x);
		fa[u] = fa[father[fa[u]]];
	}
}

int main() {
	size_t n;
	cin >> n;
	for (size_t i = 1; i != n; ++i) {
		size_t x, y;
		cin >> x >> y;
		son[x].emplace_back(y);
		father[y] = x;
	}
	vector<size_t> bfs(1, 1);
	for (size_t i = 0; i != bfs.size(); ++i) for (const auto& v : son[bfs[i]]) bfs.emplace_back(v);
	reverse(bfs.begin(), bfs.end());
	for (size_t i = 1; i <= n; ++i) cin >> w[i];
	for (size_t i = 1; i <= n; ++i) cin >> c[i];
	for (size_t i = 1; i <= n; ++i) a[i] = w[i] - c[i];
	bool check;
	auto build = [&] () {
		for (size_t i = 1; i <= n; ++i) b[i] = a[i], fa[i] = i;
		b[0] = 0;
		for (const auto& u : bfs) if (b[u] < 0) {
			b[father[u]] += b[u];
			b[u] = 0;
		}
		// cout << "b : ";
		// for (size_t i = 0; i <= n; ++i) cout << b[i] << ' ';
		// cout << endl;
		check = b[0] < int64_t(0);
	};
	build();
	size_t Q;
	cin >> Q;
	while (Q--) {
		int op;
		cin >> op;
		if (op == 1) {
			size_t A;
			int64_t B;
			cin >> A >> B;
			a[A] += B;
			build();
		}
		if (op == 2) {
			size_t A;
			int64_t B;
			cin >> A >> B;
			a[A] -= B;
			if (check) continue;
			find(A, B);
			check = b[0] < int64_t(0);
		}
		if (op == 3) {
			cout << (check ? "NO" : "YES") << endl;
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 1498ms, 内存消耗: 8700K, 提交时间: 2019-05-28 09:52:16

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100005;
int n, num, q, cnt, p[N], f[N], fa[N], c[N], h[N], e[N], pre[N];
ll w[N], a[N];
void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}
void dfs(int u){
	p[++cnt]=u;
	for(int i=h[u]; i; i=pre[i]) dfs(e[i]);
}
void rebuild(){
	for(int i=1; i<=n; ++i) a[i]=c[i];
	for(int i=n; i; --i){
		int u=p[i];
		if(a[u]>w[u]) a[f[u]=fa[u]]+=a[u]-w[u]; else f[u]=u;
	}
	for(int i=1; i<=n; ++i){
		int u=p[i];
		f[u]=f[f[u]];
	}
}
int main() {
	scanf("%d", &n);
	for(int i=1, x, y; i<n; ++i) scanf("%d%d", &x, &y), add(x, y), fa[y]=x;
	for(int i=1; i<=n; ++i) scanf("%lld", w+i);
	for(int i=1; i<=n; ++i) scanf("%d", c+i);
	dfs(1), rebuild();
	scanf("%d", &q);
	while(q--){
		int opt, x, y;
		scanf("%d", &opt);
		if(opt==3) puts(a[1]>w[1]?"NO":"YES");
		else{
			scanf("%d%d", &x, &y);
			if(opt==1) w[x]+=y, rebuild();
			else{
				w[x]-=y;
				if(f[x]!=x) a[x=find(x)]+=y;
				while(x!=1 && a[x]>w[x])
					f[x]=fa[x], a[find(x)]+=a[x]-w[x], x=f[x];
			}
		}
	}
	return 0;
}