//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;cerr<<endl;
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
int inf=4e18+5;
int mod=1e9+7;
const int MAXN=1e5+5;
int pre[MAXN],pos[MAXN];
int cnt=0;
vi c[MAXN];
void dfs(int x){
cnt++;
pre[x]=cnt;
for(int i:c[x])dfs(i);
pos[x]=cnt;
}
struct node{
int s,e,m,v,z;
node *l=nullptr,*r=nullptr;
node(int S,int E){
s=S,e=E,m=(s+e)/2;
v=0;
z=-1;
}
void cre(){
if(s==e)return;
l=new node(s,m);
r=new node(m+1,e);
}
void prop(){
if(z==-1)return;
v=z*(e-s+1);
if(s!=e){
if(l==nullptr)cre();
l->z=z;
r->z=z;
}
z=-1;
}
void ud(int S,int E,int V){
if(s==S&&e==E){
z=V;
return;
}
if(l==nullptr)cre();
if(E<=m)l->ud(S,E,V);
else if(S>m)r->ud(S,E,V);
else l->ud(S,m,V),r->ud(m+1,E,V);
prop();
l->prop(),r->prop();
v=l->v+r->v;
}
int qr(int S,int E){
prop();
if(s==S&&e==E)return v;
if(l==nullptr)cre();
if(E<=m)return l->qr(S,E);
else if(S>m)return r->qr(S,E);
else return l->qr(S,m)+r->qr(m+1,E);
}
}*root=new node(1,100005);
struct fruit{
int v,d,w;
};
bool cmp(fruit a, fruit b){
if(a.d>b.d)return 1;
else if(a.d<b.d)return 0;
else return pre[a.v]<pre[b.v];
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
//mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int n,m,k;cin>>n>>m>>k;
fruit a[m];
for(int i=2;i<=n;i++){
int p;cin>>p;
c[p].pb(i);
}
for(int i=0;i<m;i++)cin>>a[i].v>>a[i].d>>a[i].w;
dfs(1);
sort(a,a+m,cmp);
for(int i=0;i<m;i++){
int q=root->qr(pre[a[i].v],pos[a[i].v]);
if(a[i].w>=q){
root->ud(pre[a[i].v],pos[a[i].v],0);
root->ud(pre[a[i].v],pre[a[i].v],a[i].w);
}
}
cout<<root->qr(1,n)<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |