#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;
ll c[mxn];
int h[mxn];
vector<int> adj[mxn];
map<int,ll> mp[mxn];
ll suf[mxn][mxn];
int sz[mxn];
int in[mxn],out[mxn],inv[mxn];
int T = 0;
int n;
void dfs0(int u) {
sz[u] = 1;
in[u] = ++T;
inv[T] = u;
for(int v : adj[u]) {
dfs0(v);
sz[u] += sz[v];
}
out[u] = T;
}
struct BIT
{
ll bit[mxn];
void init() {
memset(bit,0,sizeof bit);
}
void update(int p,ll v) {
if(p <= 0) return;
for(;p < mxn; p += p&-p) bit[p] += v;
}
ll query(int p) {
ll r = 0;
for(;p > 0; p -= p&-p) r += bit[p];
return r;
}
void add(int l,int r,ll x) {
update(l,x);
update(r + 1, -x);
}
} bt;
void dfs(int u, bool keep = false) {
int mx = -1, bigChild = -1;
// cout<<u<<" "<<keep<<endl;
for(int v : adj[u]) {
if(sz[v] > mx) {
mx = sz[v];
bigChild = v;
}
}
for(int v : adj[u]) if(v != bigChild) dfs(v);
if(bigChild != -1) dfs(bigChild,true);
vector<int> ind;
for(int v : adj[u]) {
if(v == bigChild) continue;
int last = 0;
ll mv = mp[v][h[v]];
for(auto x : mp[v]) {
ll td = x.s;
if(x.f < h[v]) td = min(td, mv);
bt.add(last + 1, x.f, td);
last = x.f;
ind.push_back(x.f);
}
}
bt.add(1,h[u] - 1, c[u]);
bt.add(h[u] + 1, n, c[u]);
ind.push_back(h[u]);
ind.push_back(1);
ind.push_back(n);
ll nc = bt.query(h[u]);
int lo = 1;
int hi = h[u] - 1;
int pos = -1;
ll rmv = -1;
while(lo <= hi) {
int mid = lo + hi >> 1;
ll v = bt.query(mid);
if(v > nc) {
pos = mid;
rmv = v;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
if(pos != -1) {
bt.add(pos, h[u] - 1, nc - rmv);
}
// cout<<u<<" "<<h[u]<<" "<<c[u]<<endl;
// for(int i = 1; i <= n; i++) {
// cout<<"DP "<<u<<" "<<i<<" = "<<bt.query(i)<<endl;
// }
// cout<<endl<<endl;
if(!keep) {
for(int i = in[bigChild]; i <= out[bigChild]; i++) {
ind.push_back(h[inv[i]]);
}
for(int i : ind) {
mp[u][i] = bt.query(i);
}
int last = 0;
for(auto x : mp[u]) {
bt.add(last + 1, x.f, -x.s);
last = x.f;
}
}
}
int main() {
cin >> n;
vector<int> v;
for(int i = 1; i <= n; i++) {
int bap;
scanf("%d %d %lld",&bap,&h[i],&c[i]);
if(bap != i) adj[bap].push_back(i);
v.push_back(h[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()), v.end());
for(int i = 1; i <= n; i++) {
h[i] = lower_bound(v.begin(),v.end(),h[i]) - v.begin() + 1;
}
dfs0(1);
dfs(1, true);
cout<<bt.query(1)<<endl;
}
Compilation message
worst_reporter2.cpp: In function 'void dfs(int, bool)':
worst_reporter2.cpp:109:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int mid = lo + hi >> 1;
| ~~~^~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | scanf("%d %d %lld",&bap,&h[i],&c[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccMAxK4Z.o: in function `__tcf_0':
worst_reporter2.cpp:(.text+0x389): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccMAxK4Z.o
/tmp/ccMAxK4Z.o: in function `__tcf_1':
worst_reporter2.cpp:(.text+0x5aa): relocation truncated to fit: R_X86_64_PC32 against symbol `mp' defined in .bss section in /tmp/ccMAxK4Z.o
/tmp/ccMAxK4Z.o: in function `dfs0(int)':
worst_reporter2.cpp:(.text+0x63e): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccMAxK4Z.o
/tmp/ccMAxK4Z.o: in function `dfs(int, bool)':
worst_reporter2.cpp:(.text+0x785): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccMAxK4Z.o
worst_reporter2.cpp:(.text+0x841): relocation truncated to fit: R_X86_64_PC32 against symbol `h' defined in .bss section in /tmp/ccMAxK4Z.o
worst_reporter2.cpp:(.text+0x87a): relocation truncated to fit: R_X86_64_PC32 against symbol `mp' defined in .bss section in /tmp/ccMAxK4Z.o
worst_reporter2.cpp:(.text+0x9dc): relocation truncated to fit: R_X86_64_PC32 against symbol `c' defined in .bss section in /tmp/ccMAxK4Z.o
worst_reporter2.cpp:(.text+0xc11): relocation truncated to fit: R_X86_64_PC32 against symbol `mp' defined in .bss section in /tmp/ccMAxK4Z.o
worst_reporter2.cpp:(.text+0xee8): relocation truncated to fit: R_X86_64_PC32 against symbol `h' defined in .bss section in /tmp/ccMAxK4Z.o
worst_reporter2.cpp:(.text+0xf14): relocation truncated to fit: R_X86_64_PC32 against symbol `h' defined in .bss section in /tmp/ccMAxK4Z.o
/tmp/ccMAxK4Z.o: in function `main':
worst_reporter2.cpp:(.text.startup+0x10): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
