#include<bits/stdc++.h>
#define newl '\n'
const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
//struct Node{
// long long val,lazy;
// Node() : val(0),lazy(0){
//
// }
// Node(long long val,long long lazy) : val(val),lazy(lazy){
//
// }
//};
//struct SegmentTree{
// std::vector<Node> st;
// SegmentTree(int n) : st(n * 4 + 10,Node()){
//
// }
// void down(int id){
// st[id << 1].val += st[id].lazy;
// st[id << 1].lazy += st[id].lazy;
// st[id << 1 | 1].val += st[id].lazy;
// st[id << 1 | 1].lazy += st[id].lazy;
// st[id].lazy = 0;
// }
// void update(int l,int r,int u,int v,long long val,int id = 1){
// if(u <= l && r <= v){
// st[id].val += val;
// st[id].lazy += val;
// return;
// }
// down(id);
// int mid = (l + r) / 2;
// if(v <= mid){
// update(l,mid,u,v,val,id << 1);
// }
// if(u > mid){
// update(mid + 1,r,u,v,val,id << 1 | 1);
// }
// update(l,mid,u,v,val,id << 1);
// update(mid + 1,r,u,v,val,id << 1 | 1);
// st[id].val = std::max(st[id << 1].val,st[id << 1 | 1].val);
// }
// long long get(int l,int r,int u,int v,int id = 1){
// if(u <= l && r <= v){
// return st[id].val;
// }
// int mid = (l + r) / 2;
// if(v <= mid){
// return get(l,mid,u,v,id << 1);
// }
// if(u > mid){
// return get(mid + 1,r,u,v,id << 1 | 1);
// }
// return std::max(get(l,mid,u,v,id << 1),get(mid + 1,r,u,v,id << 1 | 1));
// }
//};
struct BIT{
std::vector<long long> bit;
BIT(int n) : bit(n + 1,0){
}
void update(int idx,long long val){
for(int i = idx;i < (int)bit.size();i += (i & (-i))){
bit[i] += val;
}
}
long long get(int idx){
long long ans = 0;
for(int i = idx;i > 0;i -= (i & (-i))){
ans += bit[i];
}
return ans;
}
// void updR(int l,int r){
// update(l,val);
// update(r + 1,-val);
// }
};
std::vector<int> adj[N + 1];
bool mark[N + 1];
std::map<int,long long> diff[N + 1];
int n,m,k,d[N + 1],w[N + 1],in[N + 1],out[N + 1],ver[N + 1],f[N + 1],timer = 0;
long long s[N + 1];
void readData(){
std::cin >> n >> m >> k;
std::fill(d + 1,d + n + 1,k);
for(int i = 2;i <= n;++i){
int p;
std::cin >> p;
adj[p].emplace_back(i);
}
for(int i = 1;i <= m;++i){
int v;
std::cin >> v;
std::cin >> d[v] >> w[v];
}
}
void gs(int u = 1){
f[u] = 1;
in[u] = ++timer;
ver[in[u]] = u;
for(int &v : adj[u]){
gs(v);
f[u] += f[v];
if(f[v] > f[adj[u][0]]){
std::swap(v,adj[u][0]);
}
}
out[u] = timer;
}
void solve(){
BIT bit(k);
auto add = [&](int i,long long val,std::map<int,long long> &mm){
long long s = bit.get(i);
long long upd = val - s,t = 0;
auto it = mm.upper_bound(i);
if(val < 0){
return;
}
it = mm.insert(it,{i,0});
mm[i] += upd;
while(next(it) != mm.end() && bit.get(next(it)->first) <= val){
t += next(it)->second;
bit.update(next(it)->first,-next(it)->second);
mm.erase(next(it));
}
bit.update(i,upd);
if(next(it) != mm.end()){
bit.update(next(it)->first,-upd);
bit.update(next(it)->first,t);
next(it)->second -= upd;
next(it)->second += t;
}
};
auto remov = [&](std::map<int,long long> &mm) -> void{
for(auto t : mm){
bit.update(t.first,-t.second);
}
};
auto merg = [&](std::map<int,long long> &mm,std::map<int,long long> &mm1){
for(auto t : mm1){
mm[t.first] += t.second;
bit.update(t.first,t.second);
}
};
auto dfs = [&](auto &self,int u) -> void{
for(int v : adj[u]){
if(v == adj[u][0]){
continue;
}
self(self,v);
remov(diff[v]);
}
if((int)adj[u].size()){
self(self,adj[u][0]);
std::swap(diff[u],diff[adj[u][0]]);
}
for(int v : adj[u]){
if(v == adj[u][0]){
continue;
}
merg(diff[u],diff[v]);
}
// if(u == 4){
// std::cerr << "U = " << u << newl;
// for(int i = 1;i <= k;++i){
// std::cerr << bit.get(i) << " ";
// }
// std::cerr << newl;
// for(auto t : diff[u]){
// std::cerr << t.first << " " << t.second << newl;
// }
// std::cerr << newl;
// }
s[u] = bit.get(d[u]) + w[u];
add(d[u],s[u],diff[u]);
// if(u == 4){
// std::cerr << "U = " << u << newl;
// for(int i = 1;i <= k;++i){
// std::cerr << bit.get(i) << " ";
// }
// std::cerr << newl;
// for(auto t : diff[u]){
// std::cerr << t.first << " " << t.second << newl;
// }
// std::cerr << newl;
// }
};
dfs(dfs,1);
std::cout << bit.get(k);
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
readData();
gs();
solve();
// std::map<int,long long> mm;
// BIT bit(5);
// auto add = [&](int i,long long val){
// long long s = bit.get(i);
// long long upd = val - s,t = 0;
// auto it = mm.upper_bound(i);
// if(val < 0){
// return;
// }
// it = mm.insert(it,{i,0});
// mm[i] += upd;
// while(next(it) != mm.end() && bit.get(next(it)->first) <= val){
// t += next(it)->second;
// bit.update(next(it)->first,-next(it)->second);
// mm.erase(next(it));
// }
// bit.update(i,upd);
// if(next(it) != mm.end()){
// bit.update(next(it)->first,-upd);
// bit.update(next(it)->first,t);
// next(it)->second -= upd;
// next(it)->second += t;
// }
// };
// add(1,3);
// for(auto t : mm){
// std::cout << t.second << " ";
// }
// std::cout << newl;
// add(2,5);
// std::cout << bit.get(2) << newl;
// std::cout << newl;
// for(auto t : mm){
// std::cout << t.second << " ";
// }
// std::cout << newl;
// add(1,10);
// std::cout << bit.get(4) << newl;
// for(auto t : mm){
// std::cout << t.second << " ";
// }
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
24392 KB |
Output is correct |
| 2 |
Correct |
77 ms |
23692 KB |
Output is correct |
| 3 |
Correct |
142 ms |
39040 KB |
Output is correct |
| 4 |
Correct |
94 ms |
23764 KB |
Output is correct |
| 5 |
Correct |
113 ms |
25428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7768 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
7768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
18256 KB |
Output is correct |
| 2 |
Correct |
66 ms |
17232 KB |
Output is correct |
| 3 |
Correct |
46 ms |
22576 KB |
Output is correct |
| 4 |
Correct |
31 ms |
18896 KB |
Output is correct |
| 5 |
Correct |
49 ms |
31380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
