#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;
deque<ll> xs;
};
slopes dfs(int u) {
if (u > n) {
return {-1, 0, {0, 0}};
}
slopes h;
for (int v : g[u]) {
auto f = dfs(v);
while (f.a < -1) f.a++, f.b -= f.xs.front(), f.xs.pop_front();
while (f.a + f.xs.size() > 1) f.xs.pop_back();
for (auto &x : f.xs) {
x += c[v];
}
f.b -= f.a * c[v];
h.a += f.a, h.b += f.b;
for (ll x : f.xs) h.xs.push_back(x);
}
sort(h.xs.begin(), h.xs.end());
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);
for (ll x : res.xs) {
res.b -= x;
res.a++;
if (res.a == 0) {
cout << res.b << endl;
return 0;
}
}
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... |