#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[100005], 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]);
sol += (dolje[o.x] <= 0);
b.push_back(dolje[o.x]);
gore[o.x] = gore[x] + a[o.x] - o.y;
je[o.x] = (gore[o.x] - maxi >= 0);
sol += je[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){
if(je[x]){
tu[x] = upper_bound(b.begin(), b.end(), gore[x]) - b.begin();
}
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 <= 100001 ; 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');
}
inline void scll(ll &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){
scll(a[i]);
}
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 |
3072 KB |
Output is correct |
| 2 |
Correct |
13 ms |
3200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
3372 KB |
Output is correct |
| 2 |
Correct |
18 ms |
3584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
9552 KB |
Output is correct |
| 2 |
Correct |
152 ms |
8920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
12116 KB |
Output is correct |
| 2 |
Correct |
251 ms |
13276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
15536 KB |
Output is correct |
| 2 |
Correct |
397 ms |
18216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
5564 KB |
Output is correct |
| 2 |
Correct |
68 ms |
5236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
7280 KB |
Output is correct |
| 2 |
Correct |
301 ms |
7028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
353 ms |
8816 KB |
Output is correct |
| 2 |
Correct |
353 ms |
9100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
552 ms |
10508 KB |
Output is correct |
| 2 |
Correct |
630 ms |
10828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
792 ms |
13152 KB |
Output is correct |
| 2 |
Correct |
673 ms |
14540 KB |
Output is correct |
