#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define dl(x) cout<<#x<<" is "<<endl; for(auto i:x) cout<<i<<' '; cout<<endl;
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<int,pii> fruit;
const int N = 1e5+5;
vector<int>adj[N];
int st[N], en[N], par[N];
bool cmp(fruit a, fruit b){
if(a.fi == b.fi) return st[a.se.fi] > st[b.se.fi];
else return a.fi < b.fi;
}
int cnt = 1;
void dfs(int x, int p){
st[x] = cnt++;
for(auto i: adj[x]){
if(i == p) continue;
dfs(i,x);
}
en[x] = cnt-1;
}
struct node{
int s,e,m,val=0;
node *l=nullptr, *r=nullptr;
node(int S, int E){
s=S,e=E,m=(s+e)/2;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int x, int v){
if(s==e) val = v;
else{
if(x<=m) l->upd(x,v);
else r->upd(x,v);
val = max(l->val,r->val);
}
}
int query(int S, int E){
if(s==S and e==E) return val;
if(E<=m) return l->query(S,E);
if(S>m) return r->query(S,E);
return max(l->query(S,m),r->query(m+1,E));
}
}*root;
int ans(int x, int p, int f){
if(f == 1) return root->query(st[x],st[x]);
int res = 0;
for(auto i:adj[x]){
if(i == p) continue;
res += max(ans(i,x,1), ans(i,x,0));
}
return res;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n,m,k; cin>>n>>m>>k;
for(int i=2; i<=n; i++){
int j; cin>>j;
adj[i].pb(j);
adj[j].pb(i);
par[i] = j;
}
dfs(1,-1);
fruit fruits[m];
for(int i=0; i<m; i++){
int v,d,w; cin>>v>>d>>w;
fruits[i] = {d,{v,w}};
}
sort(fruits, fruits+m, cmp);
//dd(1)
//for(auto[d,p]:fruits) cout<<d<<" "<<p.fi<<' '<<p.se<<endl;
root = new node(1,n);
int ptr = 0;
for(int day=1; day<=k; day++){
while(ptr != n and fruits[ptr].fi == day){
//dd(day)
auto[d,p] = fruits[ptr];
auto[u,w] = p;
int sum = 0;
for(auto v: adj[u]){
if(v == par[u]) continue;
sum += root->query(st[v],en[v]);
}
root->upd(st[u],sum+w);
//dd2(st[u],sum+w)
ptr++;
}
}
cout<<ans(1,-1,0);
return 0;
}
# | 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... |