Submission #1379605


Source Code Expand

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
/*#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <assert.h>*/

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e6 + 6;

int n;
ll d[N], a[N];
vector < int > g[N];

void dfs(int v, int par) {
    if (sz(g[v]) == 1) {
        d[v] = a[v];
        return;
    }
    ll sum = 0, mx = 0;
    for (auto to : g[v]) {
        if (to == par) continue;
        dfs(to, v);
        sum += d[to];
        mx = max(mx, d[to]);
    }
    ll need = sum - a[v];
    ll lim = (mx <= sum / 2 ? sum / 2 : sum - mx);
    if (lim < need) {
        cout << "NO\n";
        exit(0);
    }
    d[v] = a[v] - need;
}

int main() {
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	forn(i, 1, n) {
        cin >> a[i];
	}

	forn(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        g[x].eb(y);
        g[y].eb(x);
	}
	
	if (n == 2) {
        cout << (a[1] == a[2] ? "YES" : "NO") << "\n";
        return 0;
	}

    int root = 1;
    while (sz(g[root]) == 1) ++root;

    dfs(root, 0);

    cout << (d[root] == 0 ? "YES" : "NO") << "\n";

	return 0;
}

Submission Info

Submission Time
Task C - Cleaning
User krauch
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2139 Byte
Status WA
Exec Time 65 ms
Memory 61312 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 47
WA × 4
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt AC 61 ms 54656 KB
in10.txt AC 61 ms 54656 KB
in11.txt AC 63 ms 60032 KB
in12.txt AC 65 ms 60032 KB
in13.txt AC 61 ms 61312 KB
in14.txt AC 60 ms 60288 KB
in15.txt AC 17 ms 49408 KB
in16.txt AC 17 ms 49536 KB
in17.txt AC 17 ms 47360 KB
in18.txt AC 16 ms 47360 KB
in19.txt AC 59 ms 54656 KB
in2.txt AC 61 ms 54656 KB
in20.txt AC 60 ms 54656 KB
in21.txt AC 58 ms 54656 KB
in22.txt AC 61 ms 54656 KB
in23.txt WA 61 ms 54656 KB
in24.txt AC 61 ms 54656 KB
in25.txt AC 17 ms 49408 KB
in26.txt AC 59 ms 54656 KB
in27.txt AC 59 ms 54656 KB
in28.txt AC 17 ms 49408 KB
in29.txt AC 56 ms 54656 KB
in3.txt AC 61 ms 54656 KB
in30.txt WA 17 ms 49408 KB
in31.txt WA 64 ms 54656 KB
in32.txt WA 61 ms 54656 KB
in33.txt AC 61 ms 54656 KB
in34.txt AC 63 ms 54656 KB
in35.txt AC 63 ms 54656 KB
in36.txt AC 61 ms 54656 KB
in37.txt AC 17 ms 49408 KB
in38.txt AC 60 ms 54656 KB
in39.txt AC 60 ms 54656 KB
in4.txt AC 61 ms 54656 KB
in40.txt AC 60 ms 54656 KB
in41.txt AC 59 ms 54656 KB
in42.txt AC 61 ms 54656 KB
in43.txt AC 60 ms 54656 KB
in44.txt AC 61 ms 54656 KB
in45.txt AC 61 ms 54656 KB
in5.txt AC 61 ms 54656 KB
in6.txt AC 61 ms 54656 KB
in7.txt AC 56 ms 54400 KB
in8.txt AC 27 ms 50176 KB
in9.txt AC 61 ms 54656 KB
sample1.txt AC 17 ms 49408 KB
sample2.txt AC 17 ms 49408 KB
sample3.txt AC 17 ms 49408 KB