treesearch

Tree Search

== include(page="template/taskheader" task_id="treesearch") ==

Poveste si cerinta...

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".

h2. 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 .

h2. Date de iesire

...

In fisierul de iesire se vor afisa $M$ linii pe fiecare dintre ele aflandu-se raspunsul la $a i-a$ intrebare.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N,M ≤ 100.000$
* costurile nodurilor sunt intre $-20.000$ si $20.000$

h2. Exemplu
table(example). |_. treesearch.in |_. treesearch.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 2
  -3 4 5 6 3
  1 2
  1 3
  2 5
  2 4
  1
  2
| 12
  13

|
h3. 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 )

== include(page="template/taskfooter" task_id="treesearch") ==

3432