#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);
}
}
inline bool is( char c ) { return c >= '0' && c <= '9'; }
inline int read_int( ) {
int num;
char c;
while( !is( c = getchar_unlocked( ) ) );
num = c - '0';
while( is( c = getchar_unlocked( ) ) ) num = num * 10 + c - '0';
return num;
}
int main () {
n = read_int();
for (int i=1; i<=n; i++) {
val[i] = read_int();
}
for (int i=0; i<n-1; i++) {
int a, b, c;
a = read_int();
b = read_int();
c = read_int();
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 |
17 ms |
3064 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
424 ms |
3588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
9572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
12140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
15592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
794 ms |
5500 KB |
Output is correct |
| 2 |
Correct |
36 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
7416 KB |
Output is correct |
| 2 |
Execution timed out |
1070 ms |
7024 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
198 ms |
8820 KB |
Output is correct |
| 2 |
Correct |
149 ms |
9152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
283 ms |
10728 KB |
Output is correct |
| 2 |
Correct |
269 ms |
11060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
13080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
