#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
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 |
| 1 |
Correct |
8 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
12212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
8104 KB |
Output is correct |
| 2 |
Correct |
48 ms |
7808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
8788 KB |
Output is correct |
| 2 |
Correct |
165 ms |
8632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
9304 KB |
Output is correct |
| 2 |
Correct |
196 ms |
9272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
9796 KB |
Output is correct |
| 2 |
Correct |
296 ms |
9624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
464 ms |
10756 KB |
Output is correct |
| 2 |
Correct |
371 ms |
12256 KB |
Output is correct |
