Submission #1117659

#TimeUsernameProblemLanguageResultExecution timeMemory
1117659vjudge1Paprike (COI18_paprike)C++17
0 / 100
1175 ms1048576 KiB
// author - alimammadzade

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

const int N = 1e5 + 1;
int p[N];
int _find(int u) { return (p[u] < 0 ? u : p[u] = _find(p[u])); }
void _union(int u, int v) { p[u] += p[v], p[v] = u; }

signed main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    // system("cls"), freopen("in.txt", "r", stdin);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) { cin >> p[i]; p[i] = -p[i]; }
    int res = n - 1;
    vector<array<int, 2>> e(n - 1);
    for (auto& [u, v] : e) cin >> u >> v;
    for (auto [u, v] : e) {
        u = _find(u), v = _find(v);
        if (u != v and -p[u] - p[v] <= k) { res--; _union(u, v); }
    }
    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...