#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
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);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; ++i){
cin >> a[i];
}
for(int i = 0 ; i < n - 1 ; ++i){
int x, y;
ll w;
cin >> x >> y >> w;
ms[x].push_back(mp(y, w));
ms[y].push_back(mp(x, w));
}
decompose(1);
cout << sol << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
3200 KB |
Output is correct |
| 2 |
Correct |
14 ms |
3456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
3532 KB |
Output is correct |
| 2 |
Correct |
33 ms |
3840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
10024 KB |
Output is correct |
| 2 |
Correct |
198 ms |
10480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
365 ms |
12736 KB |
Output is correct |
| 2 |
Correct |
343 ms |
15852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
452 ms |
16288 KB |
Output is correct |
| 2 |
Correct |
523 ms |
21944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
5864 KB |
Output is correct |
| 2 |
Correct |
85 ms |
6000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
7888 KB |
Output is correct |
| 2 |
Correct |
386 ms |
8684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
523 ms |
9548 KB |
Output is correct |
| 2 |
Correct |
437 ms |
11692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
799 ms |
11716 KB |
Output is correct |
| 2 |
Correct |
650 ms |
13796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1031 ms |
13920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
