#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=100100;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;
ll A[MAXN];
vi tmin,tmout;
ll res(){
sort(ALL(tmin));
sort(ALL(tmout));
// cerr<<"Query\n";
// for(auto i:tmin)cerr<<i<<' ';cerr<<'\n';
// for(auto i:tmout)cerr<<i<<' ';cerr<<'\n';
ll X=0;
ll ans=0;
for(auto i:tmin){
while(SZ(tmout)&&tmout.back()+i>=0){
tmout.pop_back();++X;
}
ans+=X;
}
return ans;
}
ll out;
struct CD{
vi par,ban,sub;
vpi V[MAXN];
ll N;
vi allouts,allins;
CD(ll _N):N(_N){
par.resize(N,-1);
ban.resize(N,-1);
sub.resize(N,-1);
}
void build(ll u,ll p,ll l){
ll n=dfs1(u,-1);
ll cent=dfs2(u,-1,n);
par[cent]=p;
ban[cent]=l;
// cerr<<"Cent "<<cent<<'\n';
allouts.clear();allins.clear();
ll X=-1;
for(auto v:V[cent])if(ban[v.f]==-1){
tmout.clear();tmin.clear();
ll ds=A[cent]-v.s;
ll r=A[v.f]-v.s;
dfs3(v.f,cent,ds,min(0LL,ds),max(0LL,-r),r);
for(auto i:tmout)allouts.pb(i);
for(auto i:tmin)allins.pb(i);
ll t=res();
// cerr<<"Sub "<<t<<'\n';
X-=t;
}
tmout.clear();tmin.clear();
tmin.pb(0);tmout.pb(0);
for(auto i:allouts)tmout.pb(i);
for(auto i:allins)tmin.pb(i);
// cerr<<"Node "<<cent<<'\n';
// for(auto i:tmout)cerr<<i<<' ';cerr<<'\n';
// for(auto i:tmin)cerr<<i<<' ';cerr<<'\n';
X += res();
// cerr<<X<<'\n';
out += X;
for(auto v:V[cent])if(ban[v.f]==-1)build(v.f,cent,l+1);
}
ll dfs1(ll u,ll p){
// ds is the current distance already completed
sub[u]=1;
for(auto v:V[u])if(v.f!=p&&ban[v.f]==-1){
sub[u]+=dfs1(v.f,u);
}
return sub[u];
}
ll dfs2(ll u,ll p,ll n){
for(auto v:V[u])if(v.f!=p&&ban[v.f]==-1){
if(sub[v.f]>n/2)return dfs2(v.f,u,n);
}
return u;
}
void dfs3(ll u,ll p,ll ds,ll cs,ll req,ll surp){
tmout.pb(cs);
if(req<0)req=0;
if(req==0)tmin.pb(surp);
// req=min(0LL,req);
for(auto v:V[u])if(v.f!=p&&ban[v.f]==-1){
ll d=ds+A[u]-v.s;
ll ns=surp+A[v.f]-v.s;
dfs3(v.f,u,d,min(cs,d),req-A[v.f]+v.s,ns);
}
}
}*root;
ll N,a,b,w;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>N;
root=new CD(N);
for(ll i=0;i<N;++i)cin>>A[i];
for(ll i=1;i<N;++i){
cin>>a>>b>>w;--a;--b;
root->V[a].pb(b,w);
root->V[b].pb(a,w);
}
root->build(0,-1,0);
cout<<out;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3072 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3328 KB |
Output is correct |
| 2 |
Correct |
11 ms |
3584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
9520 KB |
Output is correct |
| 2 |
Correct |
65 ms |
9584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
11440 KB |
Output is correct |
| 2 |
Correct |
111 ms |
14444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
15084 KB |
Output is correct |
| 2 |
Correct |
173 ms |
19696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
5756 KB |
Output is correct |
| 2 |
Correct |
32 ms |
5836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
8048 KB |
Output is correct |
| 2 |
Correct |
96 ms |
8312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
9440 KB |
Output is correct |
| 2 |
Correct |
143 ms |
11284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
11588 KB |
Output is correct |
| 2 |
Correct |
181 ms |
13356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
279 ms |
13736 KB |
Output is correct |
| 2 |
Correct |
223 ms |
14836 KB |
Output is correct |
