#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) ((int)(x).size())
#define all(x) ((x).begin(), (x).end())
const int N = 3e5 + 5;
int n, m;
int p[N], c[N];
vector<int> g[N];
struct slopes {
ll a, b;
priority_queue<ll> l;
multiset<ll> r;
slopes() {
a = -1, b = 0;
l.push(0);
r.insert(0);
}
};
slopes dfs(int u) {
if (g[u].empty()) {
return slopes();
}
slopes h;
h.a = h.b = 0;
h.l.pop(), h.r.clear();
for (int v : g[u]) {
auto f = dfs(v);
assert(f.a + f.l.size() == 0);
while (f.r.size() > 1) f.r.erase(f.r.find(*f.r.rbegin()));
vector<ll> vec;
for (auto x : f.r) vec.push_back(x + c[v]);
f.r.clear();
for (ll i : vec) f.r.insert(i);
ll tmp = f.l.top();
f.l.pop(), f.l.push(tmp + c[v]);
f.b += c[v];
if (h.l.size() + h.r.size() < f.l.size() + f.r.size()) swap(h, f);
while (f.l.size()) {
h.l.push(f.l.top());
f.l.pop();
}
for (auto x : f.r) {
h.r.insert(x);
}
h.a += f.a, h.b += f.b;
while (!h.l.empty() && !h.r.empty() && h.l.top() > *h.r.begin()) {
h.r.insert(h.l.top());
h.l.pop();
h.l.push(*h.r.begin());
h.r.erase(h.r.begin());
}
}
return h;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 2; i <= n + m; i++) {
cin >> p[i] >> c[i];
g[p[i]].push_back(i);
}
auto res = dfs(1);
while (res.l.size()) {
res.b -= res.l.top();
res.l.pop();
}
cout << res.b << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |