/**
* APIO 2016 - Fireworks
* Solution by Gemini
* * Approach: Slope Trick with Leftist Heap
* Time Complexity: O((N+M) log(N+M))
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Leftist Heap Node
struct Node {
long long val;
int dist; // Distance to null node (for leftist property)
Node *l, *r;
Node(long long v) : val(v), dist(1), l(nullptr), r(nullptr) {}
};
// Merge two leftist heaps
Node* merge(Node* a, Node* b) {
if (!a) return b;
if (!b) return a;
// Max-Heap property: larger values on top
if (a->val < b->val) swap(a, b);
a->r = merge(a->r, b);
if (!a->l || (a->r && a->l->dist < a->r->dist)) {
swap(a->l, a->r);
}
a->dist = (a->r ? a->r->dist : 0) + 1;
return a;
}
Node* pop(Node* root) {
Node* l = root->l;
Node* r = root->r;
delete root; // Clean up memory
return merge(l, r);
}
const int MAXN = 300005;
vector<pair<int, int>> adj[MAXN]; // Adjacency list: {child, weight}
Node* heaps[MAXN];
int N, M;
int main() {
// Optimize I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> M)) return 0;
// The total number of nodes is N + M
// Input format: parents for nodes 2 to N+M
for (int i = 2; i <= N + M; ++i) {
int p;
long long w;
cin >> p >> w;
adj[p].push_back({i, (int)w});
}
// Process the tree from bottom up (Post-order traversal)
// Since node indices are topological (parents < children usually, but let's do explicit DFS)
// Actually, explicit DFS is safer.
// We can use a non-recursive approach or recursive.
// Given depth, recursive is fine. N+M = 300,000 might risk stack overflow on some systems,
// but typically 256MB stack is enough. We'll use recursive DFS.
// We need to calculate base cost: sum of all edge weights.
// The "slope trick" calculates the reduction/increase relative to a baseline.
// Specifically, f(0) = sum(all weights).
long long base_cost = 0;
// DFS lambda
// We can't use std::function efficiently for competitive programming sometimes,
// but a manual recursive function is fine.
// We'll traverse using a manual stack or just standard recursion.
// Let's use a standard recursive function defined outside or strict ordering.
// Since input P_i < i is NOT guaranteed, we must use DFS.
auto dfs = [&](auto&& self, int u) -> void {
// If leaf (Explosive)
if (adj[u].empty()) {
// Leaf cost function corresponds to slopes -1, 1 breaking at 0.
// But we process the edge to parent at the parent's level?
// No, the standard slope trick pushes the edge effect at the node.
// For a leaf, distance 0 cost is 0.
// Breakpoints at 0, 0 (slope changes -1 -> 0 -> 1).
heaps[u] = new Node(0);
heaps[u] = merge(heaps[u], new Node(0));
return;
}
for (auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
base_cost += w;
self(self, v);
// Merge child's heap into current
heaps[u] = merge(heaps[u], heaps[v]);
}
// Processing at node u (before passing to parent)
// We have merged all children.
// Current max slope is roughly equal to degree (number of children).
// We need to shape the function for the edge extending upwards from u.
// The transformation requires max slope to be 1.
// So we pop (degree - 1) largest elements.
// Note: For a leaf, we created {0, 0}. Max slope 1.
// For internal node u, we merged children.
// If u has k children, each child ends with slope 1 (after their processing).
// So sum ends with slope k.
// We want to reduce slope to 1. So pop k-1 elements.
int k = adj[u].size();
for (int i = 0; i < k - 1; ++i) {
heaps[u] = pop(heaps[u]);
}
// Now we apply the edge weight shift.
// The transformation: f_new(x) = min_y (f_old(y) + |x - y - w|)
// This shifts the "slope 0" and "slope 1" transition points by w.
// Top of heap is R (slope 1 transition).
// Next is L (slope 0 transition).
long long R = heaps[u]->val;
heaps[u] = pop(heaps[u]);
long long L = heaps[u]->val;
heaps[u] = pop(heaps[u]);
// Push shifted values
// Note: We access the parent edge weight in the caller or here?
// The problem is we need the weight of the edge ABOVE u.
// But the current logic inside `for` loop handled `base_cost` for edge u->v.
// The edge above u is handled when `dfs(parent)` calls `dfs(u)`.
// Wait, we need to apply the edge weight of u->parent NOW.
// But we don't have it easily.
// We should actually handle the "shift" logic using the edge leading TO u.
// The problem description gives edges from P to i.
// So we need to look up weight of edge parent[u] -> u.
// Actually, simpler: pass weight in DFS.
};
// Redefine DFS to take edge weight to parent
auto dfs_refined = [&](auto&& self, int u, int w_to_parent) -> void {
if (adj[u].empty()) {
// Leaf
// Initial breakpoints 0, 0.
heaps[u] = new Node(0);
heaps[u] = merge(heaps[u], new Node(0));
} else {
for (auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
base_cost += w;
self(self, v, w);
heaps[u] = merge(heaps[u], heaps[v]);
}
// Pop degree-1 elements
int k = adj[u].size();
for (int i = 0; i < k - 1; ++i) {
heaps[u] = pop(heaps[u]);
}
}
// Apply edge weight w_to_parent
// If u is root (1), w_to_parent is 0 or irrelevant (we don't shift at root).
if (u != 1) {
long long R = heaps[u]->val;
heaps[u] = pop(heaps[u]);
long long L = heaps[u]->val;
heaps[u] = pop(heaps[u]);
heaps[u] = merge(heaps[u], new Node(R + w_to_parent));
heaps[u] = merge(heaps[u], new Node(L + w_to_parent));
}
};
dfs_refined(dfs_refined, 1, 0);
// Final Calculation at Root
// The heap contains change points.
// Slope starts at -M (number of leaves).
// F(0) = base_cost.
// We integrate until slope becomes 0.
// The slope becomes 0 after M increments.
// Since heap is Max-Heap, it stores the LARGEST change points.
// The points where slope is negative are the smallest ones (deep in heap or not popped).
// The range of slopes is [-M, M]. Total 2M points.
// We want the value at the point where slope becomes 0.
// That is the M-th smallest point.
// Since we have a Max-Heap of size 2M (roughly), the M-th smallest is the (Size - M + 1)-th largest.
// Or more simply:
// We just pop elements. Each pop corresponds to a slope segment at the far right.
// Slope at far right (after last point) is M.
// Pop 1 -> slope M-1.
// ...
// Pop M -> slope 0.
// So we just need to integrate backwards from infinity?
// No, standard way:
// Sort all points. Calculate from 0.
vector<long long> points;
while (heaps[1]) {
points.push_back(heaps[1]->val);
heaps[1] = pop(heaps[1]);
}
sort(points.begin(), points.end());
// Logic:
// f(x) has slope -M at x=0.
// f(0) = base_cost.
// Points p_0, p_1, ...
// Cost at p_0 (first change point):
// f(p_0) = f(0) + slope * (p_0 - 0) = base_cost + (-M) * p_0.
// New slope = -M + 1.
// And so on.
// We stop when slope becomes 0.
long long current_cost = base_cost;
long long current_slope = -M;
long long prev_x = 0;
for (long long x : points) {
current_cost += current_slope * (x - prev_x);
current_slope++;
prev_x = x;
if (current_slope == 0) break;
}
cout << current_cost << endl;
return 0;
}
