.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » treegame

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
treegame


Timp maxim de execuţie/test:
0.5 secunde
Memorie totala disponibilă/stivă:
16MB/1 MB

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 Sj sau Sj 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.

Restricţii

  • 1 <= N <= 50000
  • 1 <= M <= 50000
  • Pentru 40% din teste M <= 2000
  • Radacina arborelui este intotdeauna nodul 1
  • Un nod este stramos si pentru el insusi
  • Daca un jucator poate muta este obligat sa o faca

Exemple

treegame.in treegame.out

4 5
4 1 1
4 1 2 3 1

3
-1
1
2
1

Silviu Ionut Ganceanu
Universitatea Politehnica Bucuresti
silviu@balaur.ro
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, basm, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: descfib, otilia, tvshow, algola, bifo, pal, evantai
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor