Fişierul intrare/ieşire:treesearch.in, treesearch.outSursăAll You Can Code 2008
AutorFlorin PogocsanAdăugată deBinary_FireFlorin Pogocsan Binary_Fire
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.intreesearch.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 )

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content