This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(int 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);
if(k==1)++z;
}
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;
z+=_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;
long long z0=z;
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]);
}
#define _assert(x) if(!(x)) __builtin_trap();
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 (stderr)
transport.c: In function 'decomp':
transport.c:112:15: warning: unused variable 'z0' [-Wunused-variable]
112 | long long z0=z;
| ^~
transport.c: In function 'main':
transport.c:137:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d",&n);
| ^~~~~~~~~~~~~~
transport.c:138:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | for(int i=1;i<=n;++i)scanf("%d",a+i);
| ^~~~~~~~~~~~~~~
transport.c:140:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | 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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |