This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* cerberus97 - Hanit Banga */
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 3e5 + 10;
int p[N];
ll c[N], val[N];
vector<int> g[N];
pair<ll, pll> solve(int u);
int main() {
fast_cin();
int n, m;
cin >> n >> m;
n += m;
for (int i = 2; i <= n; ++i) {
cin >> p[i] >> c[i];
val[i] = val[p[i]] + c[i];
g[p[i]].pb(i);
}
auto ans = solve(1);
cout << ans.first << endl;
}
pair<ll, pll> solve(int u) {
if (g[u].empty()) {
return {0, {val[u], val[u]}};
}
ll base = 0, cur = 0;
vector<pll> intervals;
for (auto &v : g[u]) {
auto i = solve(v);
base += i.first;
intervals.push_back({i.second.first, 1});
intervals.push_back({i.second.second, -1});
cur += i.second.first;
}
ll best = cur; pll best_interval = {0, 0};
int lo = 0, hi = intervals.size() / 2;
sort(intervals.begin(), intervals.end());
ll cand = 0;
for (auto &i : intervals) {
if (cand < i.first) {
cur += (i.first - cand) * (lo - hi);
cand = i.first;
if (cur < best) {
best = cur;
best_interval = {cand, cand};
} else if (cur == best) {
best_interval.second = cand;
}
}
if (i.second == 1) {
--hi;
} else {
++lo;
}
}
best += base;
// cout << u << ' ' << best << ' ' << best_interval.first << ' ' << best_interval.second << endl;
return {best, best_interval};
}
# | 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... |