Submission #1117742

#TimeUsernameProblemLanguageResultExecution timeMemory
1117742vjudge1Paprike (COI18_paprike)C++17
0 / 100
1002 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 = 0;
    vector<array<int, 2>> e(n - 1);
    for (auto& [u, v] : e) {
        cin >> u >> v;
        int pu = _find(u), pv = _find(v);
        if (pu != pv and -p[pu] - p[pv] <= k) _union(pu, pv);
    }
    for (auto& [u, v] : e) res += (_find(u) != _find(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...