/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e5+100, M = 1e5, K = 1e3+10;
struct Node{
Node *L, *R;
ll val, lazy, lazy2;
Node(){
L = R = nullptr;
val = 0;
lazy = lazy2 = 0;
}
void extend(){
if(L == nullptr) L = new Node();
if(R == nullptr) R = new Node();
}
void push(){
L->val = max(L->val + lazy, lazy2);
R->val = max(R->val + lazy, lazy2);
L->lazy += lazy;
R->lazy += lazy;
L->lazy2 = max(L->lazy2, lazy2);
R->lazy2 = max(R->lazy2, lazy2);
lazy = 0;
lazy2 = 0;
}
void range_update(int l, int r, int ql, int qr, ll x){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
val += x;
lazy += x;
return;
}
extend();
push();
int m = l+r>>1;
L->range_update(l, m, ql, qr, x);
R->range_update(m+1, r, ql, qr, x);
val = max(L->val, R->val);
}
void range_update_max(int l, int r, int ql, int qr, ll x){
if(ql > r || l > qr) return;
if(ql <= l && r <= qr){
val = max(x, val);
lazy2 = max(lazy2, x);
return;
}
extend();
push();
int m = l+r>>1;
L->range_update_max(l, m, ql, qr, x);
R->range_update_max(m+1, r, ql, qr, x);
val = max(L->val, R->val);
}
ll get(int l, int r, int p){
if(r <= p) return val;
extend();
push();
int m = l+r>>1;
if(p <= m)
return L->get(l, m, p);
return max(L->val, R->get(m+1, r, p));
}
ll gett(int l, int r, int p){
if(l >= p) return val;
extend();
push();
int m = l+r>>1;
if(p >= m + 1)
return R->gett(m+1, r, p);
return max(R->val, L->gett(l, m, p));
}
};
int n, m, k, sz[N], d[N];
vector<int> g[N], T_time[N];
ll w[N];
vector<Node*> T;
void pre(int v){
sz[v] = 1;
for(int &u: g[v]){
pre(u);
sz[v] += sz[u];
if(sz[u] > sz[g[v][0]]) swap(u, g[v][0]);
}
}
void dfs(int v){
int big = g[v].empty() ? -1 : g[v][0];
for(int u: g[v]){
dfs(u);
if(d[u] > 0){
ll val = T[u]->get(1, M, d[u]) + w[u];
T[u]->range_update_max(1, M, d[u], M, val);
T_time[u].pb(d[u]);
// cout << d[u] << ' ' << w[u] << ' ' << u << '\n';
}
}
if(big != -1){
swap(T[v], T[big]);
T_time[v].swap(T_time[big]);
}else{
T[v] = new Node();
}
for(int u: g[v]){
if(u == big) continue;
sort(all(T_time[u]), greater<int>());
int last = M;
for(int tm: T_time[u]){
if(tm > last) continue;
// cout << v << ' ' << u << ' ' << tm << '\n';
ll val = T[u]->get(1, M, tm);
// cout << val << '\n';
T[v]->range_update(1, M, tm, last, val);
T_time[v].pb(tm);
last = tm - 1;
}
}
}
void solve(){
cin >> n >> m >> k;
for(int i = 2; i <= n; ++i){
int p; cin >> p;
g[p].pb(i);
}
for(int i = 0; i <= n; ++i) d[i] = w[i] = 0;
vector<int> val;
for(int i = 0; i < m; ++i){
int v, dd, e; cin >> v >> dd >> e;
d[v] = dd;
w[v] = e;
}
T.resize(n+1);
pre(1);
dfs(1);
cout << max(T[1]->val, d[1] == 0 ? 0ll : T[1]->get(1, M, d[1]) + w[1]);
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
magictree.cpp: In member function 'void Node::range_update(int, int, int, int, long long int)':
magictree.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int m = l+r>>1;
| ~^~
magictree.cpp: In member function 'void Node::range_update_max(int, int, int, int, long long int)':
magictree.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int m = l+r>>1;
| ~^~
magictree.cpp: In member function 'long long int Node::get(int, int, int)':
magictree.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int m = l+r>>1;
| ~^~
magictree.cpp: In member function 'long long int Node::gett(int, int, int)':
magictree.cpp:76:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int m = l+r>>1;
| ~^~
magictree.cpp: In function 'int main()':
magictree.cpp:159:15: warning: unused variable 'aa' [-Wunused-variable]
159 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
5724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
130064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5976 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5980 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5980 KB |
Output is correct |
| 4 |
Correct |
86 ms |
35276 KB |
Output is correct |
| 5 |
Correct |
65 ms |
35444 KB |
Output is correct |
| 6 |
Correct |
78 ms |
35276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
88732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
5724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
5724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5724 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
5724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
