#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
const int MAXN = 100005;
llint n, root, cc, sol;
llint val[MAXN], par[MAXN], siz[MAXN], dp1[MAXN], dp2[MAXN], curr[MAXN], moze[MAXN];
bool cen[MAXN];
vector < pair <int, int> > v[MAXN];
vector <llint> q, t;
void dfs (int x, int rod) {
par[x] = rod;
siz[x] = 1;
for (int i=0; i<v[x].size(); i++) {
int sus = v[x] [i].first;
if (sus == rod || cen[sus]) continue;
dfs(sus, x);
siz[x] += siz[sus];
}
}
int nadi_centroid (int x) {
int mx = 0, ind = 0;
if (par[x] != 0) {
mx = siz[root] - siz[x];
ind = par[x];
}
for (int i=0; i<v[x].size(); i++) {
int sus = v[x] [i].first;
if (sus == par[x] || cen[sus]) continue;
if (siz[sus] > mx) {
mx = siz[sus];
ind = sus;
}
}
if (mx * 2 > n) return nadi_centroid(ind);
return x;
}
void calc_dp (int x, int rod) {
if (rod == 0) {
dp1[x] = 0;
dp2[x] = 0;
curr[x] = val[x];
}
if (rod != 0 && dp1[x] == 0) sol++;
q.push_back(dp1[x]);
for (int i=0; i<v[x].size(); i++) {
int sus = v[x] [i].first;
int dist = v[x] [i].second;
if (sus == rod || cen[sus]) continue;
dp1[sus] = max(dp1[x], -(curr[x] - dist));
curr[sus] = curr[x] - dist + val[sus];
dp2[sus] = max(0LL, dp2[x]-(val[sus] - dist));
calc_dp(sus, x);
}
}
void napravi (int x, int rod) {
t.push_back(dp1[x]);
for (int i=0; i<v[x].size(); i++) {
int sus = v[x] [i].first;
if (sus == rod || cen[sus]) continue;
napravi(sus, x);
}
}
void upit (int x, int rod) {
if (dp2[x] == 0) {
sol += upper_bound(q.begin(), q.end(), curr[x] - val[cc]) - q.begin() - 1;
sol -= upper_bound(t.begin(), t.end(), curr[x] - val[cc]) - t.begin() - 1;
}
for (int i=0; i<v[x].size(); i++) {
int sus = v[x] [i].first;
if (sus == rod || cen[sus]) continue;
upit(sus, x);
}
}
void decompose (int x) {
root = x;
dfs(root, 0);
cc = nadi_centroid(root);
cen[cc] = 1;
q.clear();
calc_dp(cc, 0);
sort(q.begin(), q.end());
for (int i=0; i<v[cc].size(); i++) {
int sus = v[cc] [i].first;
if (cen[sus]) continue;
t.clear();
napravi(sus, cc);
sort(t.begin(), t.end());
upit(sus, cc);
}
int cvor = cc;
for (int i=0; i<v[cvor].size(); i++) {
int sus = v[cvor] [i].first;
if (cen[sus]) continue;
decompose(sus);
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i=1; i<=n; i++) {
cin >> val[i];
}
for (int i=0; i<n-1; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
decompose(1);
cout << sol;
return 0;
}
Compilation message
transport.cpp: In function 'void dfs(int, int)':
transport.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
transport.cpp: In function 'int nadi_centroid(int)':
transport.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
transport.cpp: In function 'void calc_dp(int, int)':
transport.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
transport.cpp: In function 'void napravi(int, int)':
transport.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
transport.cpp: In function 'void upit(int, int)':
transport.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[x].size(); i++) {
~^~~~~~~~~~~~
transport.cpp: In function 'void decompose(int)':
transport.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[cc].size(); i++) {
~^~~~~~~~~~~~~
transport.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<v[cvor].size(); i++) {
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
3064 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
321 ms |
3396 KB |
Output is correct |
| 2 |
Correct |
447 ms |
3620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
9716 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
12136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1085 ms |
15596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
802 ms |
5620 KB |
Output is correct |
| 2 |
Correct |
40 ms |
5240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
7412 KB |
Output is correct |
| 2 |
Execution timed out |
1075 ms |
6996 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
8816 KB |
Output is correct |
| 2 |
Correct |
179 ms |
9172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
309 ms |
10712 KB |
Output is correct |
| 2 |
Correct |
302 ms |
11104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
13100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
