Problem A
Fiber Optics
Languages
en
sv
The communication network in Stackköping consists of a tree with $N$ nodes. You want to select certain edges and place fiber optic cables there. However, each node can have at most $K$ edges with fiber optic cables connected to it.
Your task is to place as many fiber optic cables as possible. But each edge also has a cost, and among all the ways to place the maximum number of fiber optic cables, you want to find the one with the minimum possible cost.
Input
The first line contains two integers $N$ and $K$ ($2 \leq N \leq 10^5$, $1 \leq K \leq 100$).
The following $N-1$ lines each contain two integers $p_i$, $w_i$ ($1 \leq p_i \leq i$, $0 \leq w_i \leq 10^9$). This means that there is an edge between the nodes with indices $p_i$ and $i+1$, with a cost $w_i$.
Output
Print two integers: the maximum number of edges, and the minimum cost for that number of edges.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$10$ |
$N \leq 15$ |
|
$2$ |
$10$ |
$K = 1$ |
|
$3$ |
$10$ |
$K \leq 2$ |
|
$4$ |
$10$ |
$N \leq 100$ |
|
$5$ |
$20$ |
$N \leq 2000$ |
|
$6$ |
$15$ |
$w_i = 0$ |
|
$7$ |
$25$ |
No additional constraints. |
| Sample Input 1 | Sample Output 1 |
|---|---|
8 2 1 0 1 0 1 0 2 0 2 0 2 0 1 0 |
4 0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 3 1 5 1 2 1 4 2 6 2 7 2 2 1 6 |
6 27 |