This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// iee
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);
template <class T> void read(T &x) {
x = 0;
int f = 1, ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch - '0');
ch = getchar();
}
x *= f;
}
int main() {
int TT = 1; // cin >> TT;
rep(CAS, 1, TT)
work(CAS);
return 0;
}
const int N = 1e5 + 5;
int n, a[N];
ll ans;
vector<pair<int, int>> e[N];
void dfs(int u, int pr = -1, ll W = 0) {
if (W < 0) return;
W += a[u], ++ans;
for (auto ver: e[u]) {
int v, w;
tie(v, w) = ver;
if (v != pr)
dfs(v, u, W - w);
}
}
void work(int CASE) {
read(n);
rep(i, 1, n) read(a[i]);
rep(i, 1, n - 1) {
int u, v, w;
read(u), read(v), read(w);
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
rep(i, 1, n) dfs(i);
cout << ans - n;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |