In timpul liber Algorel si Gigel nascocesc tot felul de jocuri. Ultima lor inventie in domeniu este foarte ciudata: Gigel deseneaza un arbore cu N noduri numerotate de la 1 la N pe o foaie de hartie, apoi tot el alege o secventa S de numere intregi, nu neaparat distincte, din intervalul [1, N] si il lasa pe prietenul sau Algorel sa aleaga pozitia de start in aceasta secventa. Cei doi muta alternativ, fiecare mutare constand in alegerea unei pozitii din S. Numarul de puncte obtinute in urma fiecarei mutari este egal cu valoarea secventei in pozitia aleasa. Punctajul final al fiecarui jucator este suma punctelor obtinute in urma mutarilor efectuate de el.
Din pozitia i se poate muta in pozitia j daca si numai daca:
i < j
Si este stramos al nodului SjsauSj este stramos al nodului Si. Spunem ca un nod x este stramos pentru un nod y daca x este situat pe drumul intre radacina arborelui si y in arborele desenat de igel.
De cand au inventat jocul Algorel vrea sa stie care este diferenta maxima dintre punctajul sau si cel al lui Gigel pe care o poate obtine pentru fiecare pozitie de start.
Cerinţă
Fiind date structura arborelui si secventa aleasa de Gigel scrieti un program care determina informatiile dorite de Algorel stiind ca Gigel joaca perfect.
Date de intrare
Prima linie a fisierului treegame.in contine doua numere intregi, N si M, reprezentand numarul de noduri din arbore si respectiv lungimea secventei S. Urmatoarea linie contine N–1 numere ce descriu structura arborelui: numarul de pe pozitia i (cu i intre 1 si N–1) este “tatal” nodului i+1 . Nodul 1 este intotdeauna radacina arborelui. Urmatoarea linie contine M numere intregi din intervalul [1, N] reprezentand secventa S. Valorile scrise pe aceeasi linie sunt separate prin spatii.
Date de ieşire
Fisierul treegame.out va contine M linii, pe linia i aflandu-se un intreg reprezentand diferenta maxima de punctaj pe care o poate obtine Algorel daca incepe jocul din pozitia i a secventei S.