레이팅 미적용A fireworks display is built as a rooted tree. Node \(1\) is the root (the ignition switch). The tree has \(N\) internal nodes (fuse-connectors, numbered \(1\) to \(N\)) and \(M\) leaf nodes (the explosives, numbered \(N+1\) to \(N+M\)). Every node except the root is connected to its parent by exactly one fuse.
When the switch is lit the fire travels along the fuses at a constant speed. For all explosives to detonate at the same instant, the total fuse length from the root to every leaf must be identical.
You may change the length of any fuse; changing a fuse of length \(\ell\) to a new non-negative integer length \(\ell'\) costs \(|\ell' - \ell|\). Find the minimum total cost to make the root-to-leaf fuse-length equal for every explosive.
\(1 \le N, M\) and \(N + M \le 300\,000\); \(1 \le C_i \le 10^9\).
- Subtask 1 (7 points): \(N = 1\).
- Subtask 2 (19 points): \(N + M \le 300\).
- Subtask 3 (29 points): \(N + M \le 5\,000\).
- Subtask 4 (45 points): \(N + M \le 300\,000\).
The first line contains two integers \(N\) and \(M\) — the number of internal nodes and the number of explosives.
Each of the next \(N + M - 1\) lines describes node \(i\) (for \(i = 2\) to \(N + M\)) with two integers \(P_i\) and \(C_i\): \(P_i\) is the parent of node \(i\) \((1 \le P_i < i)\) and \(C_i\) is the length of the fuse joining node \(i\) to its parent \((1 \le C_i \le 10^9)\).
Output a single integer: the minimum total cost so that the root-to-leaf fuse length is the same for every explosive.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 7점 | None |
Subtask 2 | 19점 | None |
Subtask 3 | 29점 | None |
Subtask 4 | 45점 | None |