#include <bits/stdc++.h>
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define task "DATA"
#define _mp make_pair
#define ll long long
#define ii pair<int, int>
#define li pair<ll, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maximize(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool minimize(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
int numNode, sz, ans = 0;
ll a[N];
vector<ii> adj[N];
int child[N], id[N];
bool del[N];
vector<li> costUp;
int bit[N];
void update(int idx, int val) {
while (idx <= sz) {
bit[idx] += val;
idx += (idx & (-idx));
}
}
int get(int idx) {
int res = 0;
while (idx > 0) {
res += bit[idx];
idx -= (idx & (-idx));
}
return res;
}
int countChild(int u, int p) {
child[u] = 1;
for (auto e : adj[u]) {
int v = e.F;
if (v == p || del[v]) continue;
child[u] += countChild(v, u);
}
return child[u];
}
int centroid(int u, int p, int m) {
for (auto e : adj[u]) {
int v = e.F;
if (v == p || del[v]) continue;
if (child[v] * 2 > m) return centroid(v, u, m);
}
return u;
}
void add(int u, int p, ll minCost, int val) {
if (minCost >= 0) update(id[u], val);
for (auto [v, w] : adj[u]) {
if (v == p || del[v]) continue;
add(v, u, min(a[v] - w, minCost + a[v] - w), val);
}
}
void up(int u, int p, ll minCost, ll sum) {
if (minCost >= 0) {
ans++;
costUp.push_back({sum, u});
}
for (auto [v, w] : adj[u]) {
if (v == p || del[v]) continue;
up(v, u, min(a[v] - w, minCost + a[v] - w), sum + a[v] - w);
}
}
void down(int u, int p, ll minCost, ll sum) {
if (minCost >= 0) ans++;
auto it = lower_bound(costUp.begin(), costUp.end(), make_pair(-minCost, -1));
if (it != costUp.end()) {
int pos = it - costUp.begin() + 1;
ans += get(sz) - get(pos - 1);
}
for (auto [v, w] : adj[u]) {
if (v == p || del[v]) continue;
down(v, u, min(minCost, sum + a[u] - w), sum + a[u] - w);
}
}
void cd(int u) {
int m = countChild(u, -1);
u = centroid(u, -1, m);
del[u] = 1;
costUp.clear();
for (auto [v, w] : adj[u]) if (!del[v])
up(v, u, a[v] - w, a[v] - w);
sort(costUp.begin(), costUp.end());
sz = costUp.size();
FOR(i, 0, sz - 1) id[costUp[i].S] = i + 1;
for (auto [v, w] : adj[u]) if (!del[v])
add(v, u, a[v] - w, 1);
for (auto [v, w] : adj[u]) {
if (del[v]) continue;
add(v, u, a[v] - w, -1);
down(v, u, a[u] - w, a[u] - w);
add(v, u, a[v] - w, 1);
}
for (auto [v, w] : adj[u]) if (!del[v])
add(v, u, a[v] - w, -1);
costUp.clear();
for (auto [v, w] : adj[u]) if (!del[v])
cd(v);
}
void main_code() {
cin >> numNode;
FOR(i, 1, numNode) cin >> a[i];
FOR(i, 1, numNode - 1) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
cd(1);
cout << ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const bool MULTITEST = 0;
int num_test = 1; if (MULTITEST) cin >> num_test;
while (num_test--) { main_code(); cout << "\n"; }
}
/* Lak lu theo dieu nhac */
Compilation message
transport.cpp: In function 'int main()':
transport.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
157 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
transport.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5800 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
11488 KB |
Output is correct |
| 2 |
Correct |
46 ms |
10332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
13532 KB |
Output is correct |
| 2 |
Correct |
81 ms |
14128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
16576 KB |
Output is correct |
| 2 |
Correct |
122 ms |
18768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
7636 KB |
Output is correct |
| 2 |
Correct |
25 ms |
7260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
9420 KB |
Output is correct |
| 2 |
Correct |
85 ms |
8528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
99 ms |
10328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
11976 KB |
Output is correct |
| 2 |
Correct |
141 ms |
11780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
13780 KB |
Output is correct |
| 2 |
Correct |
188 ms |
12884 KB |
Output is correct |
