求丁真错误,WA*5
查看原帖
求丁真错误,WA*5
726525
CuteChat楼主2024/8/23 08:41
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, a[100005], ok = 0, rt = 0;
vector<int> edges[100005];

int dfs(int i, int fa = -1) {
	int sum = 0;
	for (auto j : edges[i]) {
		if (j != fa) {
			sum += dfs(j, i);
		}
	}
	if (edges[i].size() == 1 && i != rt) return a[i];
	int k = sum - a[i];
	if (k < 0) {
		ok = 0;
		return -1;
	}
	if (a[i] < k) {
		ok = 0;
		return -1;
	}
	return a[i] - k;
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) edges[i].clear();
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	if (n == 1) {
		cout << "NO\n";
		return;
	}
	if (n == 2) {
		if (a[1] == a[2]) cout << "YES\n";
		else cout << "NO\n";
		return;
	}
	for (int i = 1; i <= n; ++i) if (edges[i].size() != 1) rt = i;
	ok = 1;
	int tmp = dfs(rt);
	if (ok && tmp == 0) cout << "YES\n";
	else cout << "NO\n";
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; /*cin >> tc;*/ while (tc--) solve();
	return 0;
}

https://atcoder.jp/contests/agc010/submissions/56989983

2024/8/23 08:41
加载中...