#include<stdio.h>
long long min_(long long a,long long b){return a<b?a:b;}
long long max_(long long a,long long b){return a>b?a:b;}
#define M 3000000
long long LIT[M],A[M],B[M];
int L[M],R[M],alc,trash[M],to;
int alloc() {int p=to?trash[--to]:++alc;L[p]=R[p]=A[p]=B[p]=LIT[p]=0;return p;}
void delet(int v){if(!v)return;trash[to++]=v;delet(L[v]);delet(R[v]);}
void pull(int v)
{
A[v]=min_(A[L[v]]+LIT[L[v]],A[R[v]]+LIT[R[v]]);
B[v]=max_(B[L[v]]+LIT[L[v]],B[R[v]]+LIT[R[v]]);
}
int same(int v){return A[v]==B[v];}
int merge(int p, int q) {
if(!p||!q)return p^q;
if(same(p)){LIT[q]+=A[p];return q;}
if(same(q)){LIT[p]+=A[q];return p;}
L[p]=merge(L[p],L[q]);
R[p]=merge(R[p],R[q]);
pull(p);
LIT[p]=0;
return p;
}
long long qry(int v,int l,int r,int p)
{
if(same(v)) return LIT[v]+A[v];
if(p<=(l+r)/2)return LIT[v]+qry(L[v],l,(l+r)/2,p);
return LIT[v]+qry(R[v],(l+r)/2+1,r,p);
}
void chmax(int v,int l,int r,int x,int y,long long k)
{
if(r<x||y<l)return;
k-=LIT[v];
if(A[v]>=k)return;
if(x<=l&&r<=y&&B[v]<=k)
{
A[v]=B[v]=k;
delet(R[v]);delet(L[v]);
return;
}
if(same(v))
{
L[v]=alloc();R[v]=alloc();
A[L[v]]=A[R[v]]=A[v];
B[R[v]]=B[L[v]]=B[v];
}
chmax(L[v],l,(l+r)/2,x,y,k); chmax(R[v],(l+r)/2+1,r,x,y,k);
pull(v);
}
#define N 100005
int n,m,k,e[N<<1][2],eo,h[N],d[N],w[N],t[N];
void dfs(int u,int p)
{
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])^p) dfs(v,u);
long long aa=w[u];
t[u]=alloc();
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])^p) t[u]=merge(t[u],t[v]);
if(~d[u])
{
aa+=qry(t[u],1,k,d[u]);
chmax(t[u],1,k,d[u],k,aa);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int p,i=2;i<=n;++i)
scanf("%d",&p),e[++eo][0]=i,e[eo][1]=h[p],h[p]=eo,d[i]=-1;
for(int vv,dd,ww,i=0;i<m;++i) scanf("%d%d%d",&vv,&dd,&ww), d[vv]=dd,w[vv]=ww;
dfs(1,1+0);
printf("%lld",LIT[1]+B[1]);
}
Compilation message
magictree.cpp: In function 'int main()':
magictree.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d%d%d",&n,&m,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~
magictree.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d",&p),e[++eo][0]=i,e[eo][1]=h[p],h[p]=eo,d[i]=-1;
| ~~~~~^~~~~~~~~
magictree.cpp:86:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | for(int vv,dd,ww,i=0;i<m;++i) scanf("%d%d%d",&vv,&dd,&ww), d[vv]=dd,w[vv]=ww;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
40020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
911 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2057 ms |
13920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
