Problem F
Melodifestligheter
Efter Melodifestivalens final ska det hållas en stor fest för alla som arbetat med att skapa denna centrala show i svensk kultur. Mia har köpt glitter, partyhattar och utfört en soundcheck på musiksystemet. Det enda som saknas är att bjuda in folk!
Mia vill skapa en så rolig fest som möjligt och åstadkommer detta genom att bjuda in så roliga medarbetare som möjligt! Varje medarbetare har nämligen ett humorindex. Men de kan dessutom vara nervösa, så om deras direkta chef är inbjuden så negeras deras humorindex (vilket innebär att negativa värden blir positiva, positiva värden blir negativa). Festens underhållningsnivå kan beskrivas av summan av humorindexen av de som är inbjudna.
Det finns en strikt hierarki bland Melodifestivalens anställda, varje person har exakt en chef, förutom VD:n som inte har någon chef. Hierarkin är dessutom stigande, ingen anställd kommer att vara chef till sin egen chef eller till sin chefs chef osv.
Indata
På första raden finns ett tal N, $1 \leq N \leq 50\, 000$, antalet anställda som arbetat med Melodifestivalens shower. På andra raden finns ett tal $h_0$, $-10^8 \leq h_0 \leq 10^8$, VD:ns humorindex.
Sedan följer $N-1$ rader som beskriver de resterande anställda, där rad $i$ (där första raden är $i=1$) beskriver anställd nummer $i$. Varje rad innehåller två tal separerade med ett mellanslag, humorindexet $h_{i}$ ($-10^8 \leq h_ i \leq 10^8$) av den anställda följt av talet som beskriver hens chef $0 \leq b_{i} \leq n-1$. VD:n beskrivs med talet $0$.
Utdata
Skriv ut den största möjliga underhållningsnivån på festen, alltså summan av humorindexen för alla inbjudna, givet den bästa kombinationen av inbjudna anställda.
Poängsättning
Din lösning kommer att testas på tre olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Begränsningar |
|
1 |
20 |
$N \leq 20$ |
|
2 |
20 |
$N \leq 500$ |
|
3 |
60 |
Inga ytterligare begränsningar |
Förklaring
I det första exempelfallet kan Mia uppnå maximal underhållning genom att bjuda in de anställda med index $1$, $2$ och $5$. Notera att eftersom att den anställda med index $1$ har ett negativt humorindex från början kommer det nu bli positivt när hens chef är på festen. Därför summeras humorindexen enligt $8 + 2 + 2 = 12$. I det andra exempelfallet uppnås maximal underhållningsnivå $7$ genom att bjuda in de anställda med index $0$ och $2$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 4 -2 2 8 0 -1 4 -3 0 2 4 |
12 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 5 3 0 2 1 -2 1 |
7 |