#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 10;
vector<int> T[N];
struct Node{
ll val;
ll lazy;
};
Node G[N * 4 + 512];
void push(int node, int cl, int cr){
G[node].val += G[node].lazy;
if(cl != cr){
G[node * 2].lazy += G[node].lazy;
G[node * 2 + 1].lazy += G[node].lazy;
}
G[node].lazy = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, ll v){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
G[node].lazy = v;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd(node * 2, cl, mid, tl, tr, v);
upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
G[node].val = max(G[node * 2].val, G[node * 2 + 1].val);
}
ll get(int node, int cl, int cr, int tl, int tr){
push(node, cl, cr);
if(cr < tl || cl > tr)
return 0ll;
if(cl >= tl && cr <= tr){
return G[node].val;
}
int mid = (cl + cr) / 2;
return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
}
int k;
int sub[N];
void dfs(int u){
sub[u] = 1;
for(auto x : T[u]){
dfs(x);
sub[u] += sub[x];
}
}
set<int> ff[N];
set<pii> res[N];
int tr[N], ww[N];
struct R{
int lef;
int rig;
ll ch;
};
vector<R> rev[N];
void dfs1(int u, bool keep){
int id = -1;
for(auto x : T[u]){
if(id == -1 || sub[x] > sub[id])
id = x;
}
for(auto x : T[u]){
if(x != id){
dfs1(x, false);
for(auto y : ff[x]){
ff[u].insert(y);
}
ff[x].clear();
}
}
if(id != -1){
dfs1(id, true);
swap(ff[u], ff[id]);
for(auto y : ff[id]){
ff[u].insert(y);
}
ff[id].clear();
swap(rev[u], rev[id]);
}
for(auto x : T[u]){
if(x != id){
int las = 0;
ll cv = -1;
for(auto y : res[x]){
if(las != 0){
upd(1, 1, k, las, y.fi - 1, y.se);
rev[u].push_back({las, y.fi - 1, y.se});
}
las = y.fi;
cv = y.se;
}
if(las != 0){
upd(1, 1, k, las, k, cv);
rev[u].push_back({las, k, cv});
}
}
}
if(tr[u] > 0){
ff[u].insert(tr[u]);
auto it = ff[u].lower_bound(tr[u]);
ll upd_val = get(1, 1, k, tr[u], tr[u]) + ww[u];
int en;
ll cur;
int st;
while(it != ff[u].end()){
st = (*it);
cur = get(1, 1, k, st, st);
if(upd_val > cur){
auto nx = ff[u].erase(it);
if(nx == ff[u].end())
en = k;
else
en = (*nx) - 1;
upd(1, 1, k, st, en, upd_val - cur);
rev[u].push_back({st, en, upd_val - cur});
it = nx;
}
else{
break;
}
}
ff[u].insert(tr[u]);
}
if(!keep){
for(auto x : ff[u]){
res[u].insert(mp(x, get(1, 1, k, x, x)));
}
for(auto f : rev[u]){
upd(1, 1, k, f.lef, f.rig, -f.ch);
}
rev[u].clear();
}
}
vector<int> sol[N];
void brute(int x){
sol[x].resize(k);
for(auto p : T[x]){
brute(p);
for(int t = 0;t < k ;t ++ )
sol[x][t] += sol[p][t];
}
if(tr[x] == 0) return;
int ts = tr[x] - 1;
int vl = sol[x][ts] + ww[x];
for(int j = ts; j < k ; j ++ ){
sol[x][j] = max(sol[x][j], vl);
}
}
int main(){
fastIO;
freopen("in.txt", "r", stdin);
int n, m;
cin >> n >> m >> k;
int p;
for(int i = 2; i <= n; i ++ ){
cin >> p;
T[p].push_back(i);
}
int id;
for(int i = 1; i <= m ; i ++ ){
cin >> id >> tr[id] >> ww[id];
}
dfs(1);
dfs1(1, true);
brute(1);
cout << sol[1][k-1] << "\n";
return 0;
}
Compilation message
magictree.cpp: In function 'int main()':
magictree.cpp:180:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
180 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
67480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
145 ms |
67608 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
130 ms |
67480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
67540 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
67480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
67480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
67480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
67480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
