| Fişierul intrare/ieşire: | treesearch.in, treesearch.out | Sursă | All You Can Code 2008 |
| Autor | Florin Pogocsan | Adăugată de |  Florin Pogocsan •Binary_Fire |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tree Search
Se da un arbore neorientat cu N noduri , fiecare avand un cost dat. Sa se raspunda la M intrebari de tipul: "care este costul maxim al unui drum ce contine nodul q si nu trece printr-un nod de mai mult de o data".
Date de intrare
Pe prima linie se afla N si M cu semnificatia din enunt. Pe urmatoare linie se afla N numere ce semnifica costul fiecarui nod. Urmeaza N-1 linii pe care se afla doi intregi ce semnifica faptul ca este muchie intre cele doua noduri. Pe urmatoarele M linii se afla cate un intreg q ce reprezinta intrebarea din enunt .
Date de iesire
In fisierul de iesire se vor afisa M linii pe fiecare dintre ele aflandu-se raspunsul la a i-a intrebare.
Restrictii
- 1 ≤ N,M ≤ 100.000
- costurile nodurilor sunt intre -20.000 si 20.000
Exemplu
| treesearch.in | treesearch.out |
|---|---|
| 5 2 -3 4 5 6 3 1 2 1 3 2 5 2 4 1 2 | 12 13 |
Explicatie
Pentru prima intrebare drumul de cost maxim este reprezentat de nodurile:
4 -> 2 -> 1 -> 3 ( 6 + 4 + (-3) + 5 = 12 )
Pentru cea de-a doua intrebare drumul este:
4 -> 2 -> 5 ( 6 + 4 + 3 = 13 )
