Problem A
Fiberoptik
Kommunikationsnätverket i Stackköping består av ett träd med $N$ noder. Du vill välja ut vissa av kanterna och lägga fiberkablar där. Men varje nod kan bara ha högst $K$ kanter med fiberkablar sammankopplade med sig.
Din uppgift är att placera ut så många fiberkablar som möjligt. Men varje kant har också en kostnad, och av alla sätt som finns att lägga ut det maximala antalet fiberkablar, så vill du hitta den minimala möjliga kostnaden.
Indata
Den första raden innehåller två heltal $N$ och $K$ ($2 \leq N \leq 10^5$, $1 \leq K \leq 100$).
De följande $N-1$ raderna innehåller två heltal $p_ i$, $w_ i$ ($1 \leq p_ i \leq i$, $0 \leq w_ i \leq 10^9$). Detta innebär att det finns en kant mellan noderna med index $p_ i$ och $i+1$, med kostnad $w_ i$.
Utdata
Skriv ut två heltal, det maximala antalet kanter, och den minimala kostnaden för det antalet kanter.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$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$ |
Inga ytterligare begränsningar |
| 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 |