#include<stdio.h>
unsigned X=12345;int rand_(){return(X*=3)>>1;}
void sort(long long*aa,int l,int r)
{
while(l<r)
{
int i=l,j=l,k=r;
long long t,p=aa[l+rand_()%(r-l)];
while(j<k)
if(aa[j]<p)
t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;
else if(aa[j]==p)
++j;
else
t=aa[--k],aa[k]=aa[j],aa[j]=t;
sort(aa,l,i);
l=k;
}
}
int t[1<<19];
void _u(int p,int k) { for(;p;p-=p&-p)t[p]+=k; }
int _q(int p) { int z=0; for(;p<sizeof t/sizeof*t;p+=p&-p)z+=t[p]; return z; }
long long cc[1<<19];
int co;
int lb(long long x)
{
int l=0,r=co-1;
while(l<=r)
{
int m=(l+r)/2;
if(cc[m]>=x)r=m-1;
else l=m+1;
}
return r+1+1;
}
long long hi(long long a,long long b) { return a>b?a:b; }
long long lo(long long a,long long b) { return a<b?a:b; }
int n,a[100001],e[200002][3],ne,h[100001],ded[100001],sz[100001];
long long ll[100001],mm[100001],ll2[100001],mm2[100001],z;
void dfs(int u,int p)
{
sz[u]=1;for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])dfs(e[j][0],u),sz[u]+=sz[e[j][0]];
}
int cen(int u,int p,int tn)
{
for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]]&&sz[e[j][0]]*2>=tn)return cen(e[j][0],u,tn);
return u;
}
void dfs2(int u,int p)
{
for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])
{
ll[e[j][0]]=a[e[j][0]]-e[j][1]+ll[u];
mm[e[j][0]]=lo(mm[u],0)+(a[e[j][0]]-e[j][1]);
ll2[e[j][0]]=ll2[u]+a[u]-e[j][1];
mm2[e[j][0]]=lo(mm2[u],ll2[e[j][0]]);
dfs2(e[j][0],u);
}
cc[co++]=ll[u];
cc[co++]=mm2[u];
}
void dfs3(int u,int p,int k)
{
if(mm[u]>=0) _u(lb(ll[u]),k), z+=(k==1);
for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])dfs3(e[j][0],u,k);
}
void dfs4(int u,int p,int k)
{
if(mm2[u]>=0) z+=k+_q(1);
else z+=_q(lb(-mm2[u]));
for(int j=h[u];j;j=e[j][2])if(e[j][0]-p&&!ded[e[j][0]])dfs4(e[j][0],u,k);
}
void decomp(int u)
{
dfs(u,-1);
u=cen(u,-1,sz[u]);
ded[u]=1;
co=ll[u]=mm[u]=ll2[u]=mm2[u]=0;
dfs2(u,-1);
sort(cc,0,co);
for(int j=h[u];j;j=e[j][2])if(!ded[e[j][0]]) dfs4(e[j][0],u,1), dfs3(e[j][0],u,1);
for(int j=h[u];j;j=e[j][2])if(!ded[e[j][0]]) dfs3(e[j][0],u,-1), dfs4(e[j][0],u,0);
for(int j=h[u];j;j=e[j][2])if(!ded[e[j][0]]) decomp(e[j][0]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",a+i);
for(int i=1,u,v,w;i<n;++i)
scanf("%d%d%d",&u,&v,&w),e[++ne][0]=v,e[ne][1]=w,e[ne][2]=h[u],h[u]=ne,e[++ne][0]=u,e[ne][1]=w,e[ne][2]=h[v],h[v]=ne;
decomp(1);
printf("%lld",z);
}
Compilation message
transport.c: In function 'main':
transport.c:103:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d",&n);
| ^~~~~~~~~~~~~~
transport.c:104:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | for(int i=1;i<=n;++i)scanf("%d",a+i);
| ^~~~~~~~~~~~~~~
transport.c:106:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%d%d",&u,&v,&w),e[++ne][0]=v,e[ne][1]=w,e[ne][2]=h[u],h[u]=ne,e[++ne][0]=u,e[ne][1]=w,e[ne][2]=h[v],h[v]=ne;
| ^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
4988 KB |
Output is correct |
| 2 |
Correct |
13 ms |
5124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
11532 KB |
Output is correct |
| 2 |
Correct |
118 ms |
11300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
13136 KB |
Output is correct |
| 2 |
Correct |
204 ms |
13312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
265 ms |
14924 KB |
Output is correct |
| 2 |
Correct |
333 ms |
15952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
47 ms |
7768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
8784 KB |
Output is correct |
| 2 |
Correct |
169 ms |
8756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
9580 KB |
Output is correct |
| 2 |
Correct |
193 ms |
9252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
285 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
281 ms |
9932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
413 ms |
10884 KB |
Output is correct |
| 2 |
Correct |
379 ms |
10128 KB |
Output is correct |
