Submission #34811094

---

Source Code Expand

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e5 + 5;

int n;
std::vector<int> g[N];
int a[N];
i64 up[N];
bool flag;
int root;

void dfs(int u, int fa) {
    if ((int)g[u].size() == 1) {
        up[u] = a[u];
        return; 
    }
    i64 sum = 0, mx = 0;
    for (auto v : g[u]) {
        if (v != fa) {
            dfs(v, u); 
            sum += up[v];
            mx = std::max(mx, up[v]);
            std::cerr << "debug: " << u << ' ' << v << ' ' << up[v] << '\n';
        }
    }
    i64 x = sum - a[u];
    i64 y = 2 * a[u] - sum;
    if (u == root) {
    	std::cerr << "dbg:" << x << ' ' << y << ' ' << mx << ' ' << a[u] << '\n';
	}
    if (x < 0 || y < 0 || mx > a[u]) {
        flag = 0;
    }
    up[u] = y; 
    std::cerr << "node : " << u << ' ' << y << '\n';

    if (u == root && y != 0) {
        flag = 0; 
    }
}

int main() {
	memset(up, 0, sizeof up);
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> 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);
    }
    if (n == 2) {
    	std::cout << (a[1] == a[2] ? "YES" : "NO") << '\n';
    	return 0; 
	}
    flag = 1;
    for (int i = 1; i <= n; i++) {
        if ((int)g[i].size() > 1) {
            root = i; 
            break;
        }
    } 
    dfs(root, 0);
    std::cout << (flag ? "YES" : "NO") << '\n';
    return 0; 
}

Submission Info

Judge Result