#include<stdio.h>
#define M 3000000
int _t[M],_l[M],_r[M],_al=1;
void _p(int v,long long l,long long r)
{
if(!_l[v])
{
_l[v]=++_al;
_r[v]=++_al;
}
}
void _u(int v,long long l, long long r,long long p,int k)
{
if(l==r)
{
_t[v]+=k;
return;
}
_p(v,l,r);
if(p<=(l+r)/2)
_u(_l[v],l,(l+r)/2,p,k);
else _u(_r[v],(l+r)/2+1,r,p,k);
_t[v]=_t[_l[v]]+_t[_r[v]];
}
int _q(int v,long long l,long long r,long long x,long long y)
{
if(r<x||y<l)return 0;
if(x<=l&&r<=y)return _t[v];
_p(v,l,r);
return (_l[v]?_q(_l[v],l,(l+r)/2,x,y):0)
+ (_r[v]?_q(_r[v],(l+r)/2+1,r,x,y):0);
}
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];
long long 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);
}
}
void dfs3(int u,int p,int k)
{
if(mm[u]>=0)
{
_u(1,0,1e15,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+=_t[1];
}
else
{
z+=_q(1,0,1e15,-mm2[u],1e15);
}
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;
ll[u]=mm[u]=ll2[u]=mm2[u]=0;
dfs2(u,-1);
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:98:15: warning: unused variable 'z0' [-Wunused-variable]
98 | long long z0=z;
| ^~
transport.c: In function 'main':
transport.c:122:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%d",&n);
| ^~~~~~~~~~~~~~
transport.c:123:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | for(int i=1;i<=n;++i)scanf("%d",a+i);
| ^~~~~~~~~~~~~~~
transport.c:125:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | 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 |
20 ms |
8272 KB |
Output is correct |
| 2 |
Correct |
28 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
14992 KB |
Output is correct |
| 2 |
Correct |
43 ms |
11860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2334 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2560 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2593 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
37712 KB |
Output is correct |
| 2 |
Correct |
144 ms |
18516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
25936 KB |
Output is correct |
| 2 |
Correct |
433 ms |
34644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
592 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
716 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
678 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
