#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 30, MOD = 1e9 + 7;
#define int ll
int n,m;
vector<pair<int,int>> g[N];
multiset<ll> st[N];
ll h[N],l[N],r[N];
int mx[N];
void merge(int v,int to){
mx[v]++;
if((int)st[v].size() < (int)st[to].size()){
st[v].swap(st[to]);
}
for(int j:st[to]){
st[v].insert(j);
}
}
ll dist(int to,ll x){
if(x >= r[to]){
return h[to] + x - r[to];
}
if(x >= l[to]) return h[to];
st[to].erase(st[to].find(r[to]));
ll ret = h[to],f = h[to] + l[to] - x;
for(ll j:st[to]){
if(j >= x && j <= l[to]){
ll val = (j - x);
ret += val;
}
}
// cout << f << ' ' << ret << "A\n";
st[to].insert(r[to]);
return ret;
}
void dfs(int v,int W = 0){
if(g[v].empty()){
st[v].insert(W);
st[v].insert(W);
mx[v] = 1;
h[v] = 0;
l[v] = r[v] = W;
return;
}
for(auto [to,w]:g[v]){
dfs(to,w);
merge(v,to);
}
while(mx[v] > 1){
mx[v]--;
st[v].erase(st[v].find(*st[v].rbegin()));
}
ll x = (*st[v].rbegin());
st[v].erase(st[v].find(*st[v].rbegin()));
ll y = (*st[v].rbegin());
st[v].erase(st[v].find(*st[v].rbegin()));
st[v].insert(x + W);
st[v].insert(y + W);
r[v] = (*st[v].rbegin());
l[v] = (*(++(st[v].rbegin())));
for(auto [to,w]:g[v]){
h[v] += dist(to,r[v] - W);
}
}
void test(){
cin >> n >> m;
for(int i = 2;i <= n + m;i++){
int a,b;
cin >> a >> b;
g[a].push_back({i,b});
if(a == 1){
P = i;
}
}
dfs(1);
cout << h[1] << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--){
test();
}
}
Compilation message
fireworks.cpp: In function 'll dist(ll, ll)':
fireworks.cpp:29:20: warning: unused variable 'f' [-Wunused-variable]
29 | ll ret = h[to],f = h[to] + l[to] - x;
| ^
fireworks.cpp: In function 'void test()':
fireworks.cpp:76:13: error: 'P' was not declared in this scope
76 | P = i;
| ^
