#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif
#include <cassert>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#ifdef Sublime
#include <iostream>
#include <sstream>
#define cin cin__
namespace std{std::stringstream cin(R"(
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
)");}
#endif // Sublime
template <typename T>
std::multiset<T> merge(std::multiset<T> a, std::multiset<T> b) {
if (a.size() < b.size()) std::swap(a, b);
a.insert(b.begin(), b.end()); // move iterator?
return a;
}
struct function {
int zero_slope; // negative
int64_t zero_value;
std::multiset<int64_t> switches;
}; // convex piecewise-linear function
// with derivative delta of (multiple of) 1
function operator+(function a, function b) {
return {
a.zero_slope + b.zero_slope,
a.zero_value + b.zero_value,
merge(std::move(a.switches), std::move(b.switches))
};
}
struct node {
size_t parent; int64_t parent_len;
// consider the function **after** connected to parent.
function fn;
};
std::istream& operator >> (std::istream& str, node & a) {
str >> a.parent >> a.parent_len;
--a.parent;
return str;
}
int main() {
size_t nbranch, nleaf;
std::cin >> nbranch >> nleaf;
std::vector<node> nodes (nbranch + nleaf);
// read input
for (size_t i = 1; i < nodes.size(); ++i) {
std::cin >> nodes[i];
}
for (size_t i = nodes.size(); i --> 1; ) {
node& n = nodes[i];
if (i >= nbranch) { // process leaves
n.fn.switches.insert({
n.parent_len,
n.parent_len}); // twice
n.fn.zero_slope = 1;
n.fn.zero_value = n.parent_len;
} else { // branches
// so now n.fn is the sum of the (fn)'s
// of the node's children.
for (int i = n.fn.switches.size() -
(n.fn.zero_slope + 1); i --> 0;)
n.fn.switches.erase(--n.fn.switches.end());
n.fn.zero_value += n.parent_len;
auto a = --n.fn.switches.end(); auto _a = *a; n.fn.switches.erase(a);
auto b = --n.fn.switches.end(); auto _b = *b; n.fn.switches.erase(b);
n.fn.switches.insert({_a + n.parent_len, _b + n.parent_len});
assert((int) n.fn.switches.size() == n.fn.zero_slope + 1);
}
// add to its parent
nodes[n.parent].fn = std::move(nodes[n.parent].fn) + std::move(n.fn);
}
function f = std::move(nodes[0].fn);
assert((int) f.switches.size() >= f.zero_slope);
for (int i = f.switches.size() - f.zero_slope; i --> 0;)
f.switches.erase(--f.switches.end());
assert((int) f.switches.size() == f.zero_slope);
int last_slope = f.zero_slope;
int64_t last_x = 0, last_y = f.zero_value;
for (int64_t x : f.switches) {
last_y -= last_slope * (x - last_x);
last_x = x;
--last_slope;
}
assert(last_slope == 0);
std::cout << last_y << '\n';
return 0;
}
