#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
vector<int>g[100005];
int depth[100005];
int d[100005];
int w[100005];
int a[100005];
bool cmp(int l,int r){
if(d[l]==d[r])return depth[l]>depth[r];
return d[l]<d[r];
}
int timer;
int tin[100005];
int tout[100005];
int n,m,k;
void dfs(int v){
tin[v]=++timer;
for(int to:g[v]){
depth[to]=depth[v]+1;
dfs(to);
}
tout[v]=timer;
}
ll tree[400005];
void update(int v,int l,int r,int pos,ll val){
tree[pos]=val;
}
ll query(int l,int r){
ll ans=0;
for(int i=l;i<=r;i++)umax(ans,tree[i]);
return ans;
}
/*void update(int v,int l,int r,int pos,ll val){
if(l==r){
tree[v]=pos;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)update(v<<1,l,mid,pos,val);
else update(v<<1|1,mid+1,r,pos,val);
tree[v]=max(tree[v<<1],tree[v<<1|1]);
}
ll get(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return 0ll;
if(ql<=l&&r<=qr)return tree[v];
int mid=(l+r)>>1;
return max(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid+1,r,ql,qr));
}
ll query(int l,int r){
if(l>r)return 0ll;
return get(1,1,n,l,r);
}*/
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=2;i<=n;i++){
int x;
scanf("%d",&x);
g[x].push_back(i);
}
while(m--){
int v;
scanf("%d",&v);
scanf("%d%d",&d[v],&w[v]);
}
dfs(1);
iota(a+1,a+1+n,1);
sort(a+1,a+1+n,cmp);
for(int i=n;i>0;i--){
int &v=a[i];
update(1,1,n,tin[v],max(query(1,tin[v]-1),query(tout[v]+1,n))+w[v]);
}
cout<<query(1,n);
}
Compilation message
magictree.cpp: In function 'int main()':
magictree.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d%d%d",&n,&m,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~
magictree.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
magictree.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d",&v);
| ~~~~~^~~~~~~~~
magictree.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d",&d[v],&w[v]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
7192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 4 |
Execution timed out |
2080 ms |
13212 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2084 ms |
7484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
428 ms |
3612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
