#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair <int, ll> pil;
#define x first
#define y second
#define mp make_pair
ll a[100005], dolje[100005], gore[100005];
vector <pil> ms[100005];
bool bio[100005], je[100005];
int br, ss[100005], tu[100005], tam[100005], f[200005], n;
vector <ll> b;
const ll inf = (ll)1e15;
void dfs1(int x, int p){
br++;
ss[x] = 1;
for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = (*i).x;
if(o == p || bio[o])
continue;
dfs1(o, x);
ss[x] += ss[o];
}
}
int dfs2(int x, int p){
for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = (*i).x;
if(o == p || bio[o])
continue;
if(ss[o] > br / 2)
return dfs2(o, x);
}
return x;
}
ll sol;
void initdp(int x, int p, ll sad, ll maxi){
for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
pil o = *i;
if(o.x == p || bio[o.x])
continue;
dolje[o.x] = max(sad - a[x] + o.y, dolje[x]);
if(dolje[o.x] <= 0){
sol++;
}
b.push_back(dolje[o.x]);
gore[o.x] = gore[x] + a[o.x] - o.y;
je[o.x] = (gore[o.x] - maxi >= 0);
if(je[o.x]){
sol++;
}
b.push_back(gore[o.x]);
initdp(o.x, x, sad - a[x] + o.y, max(maxi, gore[o.x]));
}
}
void dfs3(int x, int p){
if(p != -1){
tu[x] = lower_bound(b.begin(), b.end(), gore[x]) - b.begin() + 1;
tam[x] = lower_bound(b.begin(), b.end(), dolje[x]) - b.begin() + 1;
}
for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = (*i).x;
if(o == p || bio[o])
continue;
dfs3(o, x);
}
}
void update(int x, int y){
for(int i = x ; i <= 200001 ; i += (i & -i)){
f[i] += y;
}
}
int sum(int x){
int ret = 0;
for( ; x > 0 ; x -= (x & -x)){
ret += f[x];
}
return ret;
}
void dfs4(int x, int p, int add){
if(p != -1){
update(tam[x], add);
}
for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = (*i).x;
if(o == p || bio[o])
continue;
dfs4(o, x, add);
}
}
ll dfs5(int x, int p){
ll ret = 0;
if(je[x]){
ret += sum(tu[x]);
}
for(vector <pil>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
int o = (*i).x;
if(o == p || bio[o])
continue;
ret += dfs5(o, x);
}
return ret;
}
void decompose(int root){
br = 0;
dfs1(root, -1);
int centroid = dfs2(root, -1);
bio[centroid] = 1;
dolje[centroid] = -inf;
gore[centroid] = 0;
b.clear();
initdp(centroid, -1, 0, 0);
b.push_back(0LL);
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
/*
for(int i = 0 ; i < (int)b.size() ; ++i){
cout << b[i] << ":";
}
cout << " . ";
*/
dfs3(centroid, -1);
dfs4(centroid, -1, 1);
//cout << centroid << " - ";
for(vector <pil>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
pil o = *i;
if(bio[o.x])
continue;
dfs4(o.x, centroid, -1);
sol += dfs5(o.x, centroid);
//cout << "[" << dfs5(o.x, centroid) << "] ";
dfs4(o.x, centroid, 1);
}
//cout << endl;
dfs4(centroid, -1, -1);
for(vector <pil>::iterator i = ms[centroid].begin() ; i != ms[centroid].end() ; ++i){
int o = (*i).x;
if(bio[o])
continue;
decompose(o);
}
}
inline void sc(int &x){
register int c;
x = 0;
do{
c = getchar();
}while(c < '0');
do{
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}while(c >= '0');
}
int main(){
sc(n);
for(int i = 1 ; i <= n ; ++i){
int x;
sc(x);
a[i] = x;
}
for(int i = 0 ; i < n - 1 ; ++i){
int x, y, w;
sc(x);
sc(y);
sc(w);
ms[x].push_back(mp(y, w));
ms[y].push_back(mp(x, w));
}
decompose(1);
printf("%lld\n", sol);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
3200 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
25 ms |
3760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
9856 KB |
Output is correct |
| 2 |
Correct |
191 ms |
9316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
12632 KB |
Output is correct |
| 2 |
Correct |
329 ms |
14064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
451 ms |
16084 KB |
Output is correct |
| 2 |
Correct |
546 ms |
19300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
5784 KB |
Output is correct |
| 2 |
Correct |
91 ms |
5360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
7932 KB |
Output is correct |
| 2 |
Correct |
347 ms |
7612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
541 ms |
9452 KB |
Output is correct |
| 2 |
Correct |
443 ms |
9832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
875 ms |
11364 KB |
Output is correct |
| 2 |
Correct |
825 ms |
11876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1008 ms |
13944 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
