#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
int n,m,k,p[MAXN],a,d,w,sz[MAXN],heavy[MAXN];
pair<int,int> cost[MAXN];
vector<int> v[MAXN];
struct event{
int l,r;
long long val;
};
struct ST{
struct node{
long long mins,maxs;
long long setv,addv;
inline friend node operator + (node fr,node sc){
return {min(fr.mins,sc.mins),max(fr.maxs,sc.maxs),-1,0};
}
};
node tree[4*MAXN];
vector<event> w;
void combine(node &v,long long s,bool type){
if(!type){
v.mins+=s; v.maxs+=s; v.addv+=s;
}else{
v.mins=v.maxs=s; v.setv=s; v.addv=0;
}
}
void psh(int v){
if(tree[v].setv!=-1){
combine(tree[2*v],tree[v].setv,true);
combine(tree[2*v+1],tree[v].setv,true);
tree[v].setv=-1;
}
if(tree[v].addv!=0){
combine(tree[2*v],tree[v].addv,false);
combine(tree[2*v+1],tree[v].addv,false);
tree[v].addv=0;
}
}
void update(int v,int l,int r,int ll,int rr,long long s,bool type){
if(ll>rr)return;
if(l==ll and r==rr){
combine(tree[v],s,type);
}else{
psh(v);
int tt=(l+r)/2;
update(2*v,l,tt,ll,min(tt,r),s,type);
update(2*v+1,tt+1,r,max(tt+1,ll),rr,s,type);
tree[v]=tree[2*v]+tree[2*v+1];
}
}
long long getval(int v,int l,int r,int pos){
if(l==r)return tree[v].mins;
psh(v);
int tt=(l+r)/2;
if(pos<=tt)return getval(2*v,l,tt,pos);
else return getval(2*v+1,tt+1,r,pos);
}
void dfs(int v,int l,int r){
if(tree[v].mins==tree[v].maxs){
if(w.empty() or w.back().val!=tree[v].mins){
w.push_back({l,r,tree[v].mins});
}else w.back().r=r;
}else{
int tt=(l+r)/2;
psh(v);
dfs(2*v,l,tt);
dfs(2*v+1,tt+1,r);
}
}
void init(){
w.clear();
update(1,1,k,1,k,0,true);
}
}seg;
void dfs(int x){
sz[x]=1;
for(int i=0;i<v[x].size();i++){
dfs(v[x][i]);
sz[x]+=sz[v[x][i]];
if(sz[v[x][i]]>sz[heavy[x]])heavy[x]=v[x][i];
}
}
void solve(int x){
vector<event> s;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==heavy[x])continue;
solve(v[x][i]);
seg.dfs(1,1,k);
for(event curr:seg.w){
s.push_back(curr);
}
seg.init();
}
if(heavy[x]!=0){
solve(heavy[x]);
}
for(event curr:s){
seg.update(1,1,k,curr.l,curr.r,curr.val,false);
}
if(cost[x].first==0)return;
long long newval=seg.getval(1,1,k,cost[x].first)+cost[x].second;
int l=cost[x].first,r=k+1,tt;
while(l+1<r){
tt=(l+r)/2;
if(seg.getval(1,1,k,tt)<newval){
l=tt;
}else{
r=tt;
}
}
seg.update(1,1,k,cost[x].first,l,newval,true);
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=2;i<=n;i++){
cin>>p[i];
v[p[i]].push_back(i);
}
dfs(1);
for(int i=1;i<=m;i++){
cin>>a>>d>>w;
cost[a]={d,w};
}
solve(1);
cout<<seg.tree[1].maxs<<"\n";
return 0;
}
Compilation message
magictree.cpp: In function 'void dfs(int)':
magictree.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
magictree.cpp: In function 'void solve(int)':
magictree.cpp:106:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
119 ms |
16024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2908 KB |
Output is correct |
2 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
8272 KB |
Output is correct |
2 |
Correct |
40 ms |
8532 KB |
Output is correct |
3 |
Correct |
39 ms |
13904 KB |
Output is correct |
4 |
Correct |
29 ms |
10584 KB |
Output is correct |
5 |
Correct |
37 ms |
20820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
7516 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |