#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = (int)1e5 + 10;
const ll inf = 1e18;
struct node{
ll eq=-1;
ll add;
ll pushmx;
node(){
eq = 0;
add = 0;
pushmx = 0;
}
};
node seg[4*N];
void push(int v){
int v1 = v << 1;
for(auto &u : {v1 , v1|1}){
if(seg[v].eq != -1){
seg[u].eq=seg[v].eq,seg[u].add=0,seg[u].pushmx=seg[v].pushmx;
}else{
if(seg[u].eq!=-1)
seg[u].eq+=seg[v].add,seg[u].pushmx+=seg[v].add;
else{
seg[u].add+=seg[v].add;
seg[u].pushmx+=seg[v].add;
}
seg[u].pushmx=max(seg[u].pushmx,seg[v].pushmx);
}
}
seg[v].eq = -1;
seg[v].add = 0;
seg[v].pushmx = 0;
}
void doadd(int v , int tl , int tr , int l , int r , ll x){
if(tl == l && tr == r){
if(seg[v].eq!=-1){
seg[v].eq += x;
}else
seg[v].add += x;
seg[v].pushmx += x;
return;
}
push(v);
int mid = (tl + tr) >> 1, v1 = v << 1;
if(l <= mid)
doadd(v1 , tl , mid , l , min(r , mid) , x);
if(r > mid)
doadd(v1|1, mid + 1 , tr , max(l , mid + 1) , r , x);
// pull(v);
}
ll get(int v , int tl , int tr , int pos){
if(tl == tr){
return seg[v].pushmx;
}
push(v);
int mid = (tl + tr) >> 1, v1 = v << 1;
if(pos <= mid)
return get(v1, tl , mid , pos);
return get(v1|1,mid+1,tr,pos);
}
void domx(int v , int tl, int tr , int l , int r , ll x){
if(tl == l && tr == r){
seg[v].pushmx = max(seg[v].pushmx , x);
return;
}
push(v);
int mid = (tl + tr) >> 1 , v1 = v << 1;
if(l <= mid)
domx(v1 , tl , mid , l , min(r , mid) , x);
if(r > mid)
domx(v1|1,mid+1,tr,max(l,mid+1),r,x);
}
vector < int > g[N];
int ripeday[N], w[N];
vector < int > *vert[N];
vector<pair<int,ll>>temp[N];
int sz[N];
void sizes(int v){
sz[v] = 1;
for(auto &u : g[v]){
sizes(u);
sz[v] += sz[u];
}
}
void gozero(){
seg[1].eq = 0;
seg[1].add=0,seg[1].pushmx=0;
}
void dfs(int v){
// cerr << v << ' ' << endl;
int big = -1;
for(auto &u : g[v]){
if(big == -1 || sz[u] > sz[big])
big = u;
}
for(auto &u : g[v]){
if(u != big){
/// what do we do man?
dfs(u);
/// okay now
if(vert[u]!=nullptr){
for(auto &d : (*vert[u])){
ll x = get(1,0,N-1,d);
temp[u].push_back({d , x});
}
}
gozero();
}
}
if(big == -1){
if(ripeday[v] != -1){
doadd(1,0,N-1, ripeday[v], N-1, w[v]);
vert[v] = new vector<int>;
(*vert[v]).push_back(ripeday[v]);
}
}else{
dfs(big);
vert[v] = vert[big];
for(auto &u : g[v]){
if(u != big){
if(temp[u].empty())continue;
sort(all(temp[u]));
temp[u].erase(unique(all(temp[u])) , temp[u].end());
int prv = -1;
for(int i = 0; i < sz(temp[u]); ++i){
if(i - 1 >= 0){
assert(temp[u][i-1].se <= temp[u][i].se);
assert(temp[u][i-1].fi != temp[u][i].fi);
}
int rb = (i == sz(temp[u]) - 1 ? N-1 : temp[u][i + 1].fi - 1);
doadd(1 , 0 , N - 1, temp[u][i].fi, rb, temp[u][i].se);
}
temp[u].clear();
for(auto &x : (*vert[u]))
(*vert[v]).push_back(x);
}
}
if(ripeday[v] != -1){
ll t = get(1 , 0 , N - 1 , ripeday[v]);
t += w[v];
domx(1 , 0 , N -1 , ripeday[v], N - 1 , t);
(*vert[v]).push_back(ripeday[v]);
}
}
}
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0) , cout.tie(0);
int n , m, k;
cin >> n >> m >> k;
for(int i = 1; i < n; ++i){
int p;cin >> p, --p;
g[p].pb(i);
}
fill(ripeday , ripeday + N , -1);
for(int i = 0; i < m; ++i){
int v , d;
cin >> v >> d;
--v;
cin >> w[v];
ripeday[v] = d;
}
sizes(0);
dfs(0);
ll ans = 0;
for(int t=0;t<N-1;++t){
ans = max(ans , get(1 , 0 , N - 1, t));
}
cout << ans;
return 0;
}
/*
5 0 1
1 1 1 1
*/
Compilation message
magictree.cpp: In function 'void dfs(int)':
magictree.cpp:140:21: warning: unused variable 'prv' [-Wunused-variable]
140 | int prv = -1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
14812 KB |
Output is correct |
| 2 |
Correct |
25 ms |
14804 KB |
Output is correct |
| 3 |
Runtime error |
18 ms |
29780 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
34304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
14932 KB |
Output is correct |
| 2 |
Correct |
32 ms |
14988 KB |
Output is correct |
| 3 |
Correct |
27 ms |
14932 KB |
Output is correct |
| 4 |
Correct |
106 ms |
34104 KB |
Output is correct |
| 5 |
Correct |
113 ms |
34000 KB |
Output is correct |
| 6 |
Correct |
159 ms |
34204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
35216 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
14812 KB |
Output is correct |
| 2 |
Correct |
25 ms |
14804 KB |
Output is correct |
| 3 |
Runtime error |
18 ms |
29780 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
30804 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
14812 KB |
Output is correct |
| 2 |
Correct |
25 ms |
14804 KB |
Output is correct |
| 3 |
Runtime error |
18 ms |
29780 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
14812 KB |
Output is correct |
| 2 |
Correct |
25 ms |
14804 KB |
Output is correct |
| 3 |
Runtime error |
18 ms |
29780 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
