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

Se da un arbore neorientat cu $N$ noduri , fiecare avand un cost dat. Sa se raspunda la $M$ intrebari de tipul: "care este drumul de cost maxim ce contine nodul $q$".

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

h2. Restrictii
* $1 ≤ N,M ≤ 100.000$

* $costurile nodurilor sunt intre -1000 si 1000$

* costurile nodurilor sunt intre $-20.000$ si $20.000$

h2. Exemplu

  2 5
  2 4
  1

  4

  2

| 12
  13
|
h3. Explicatie

Pentru prima intrebare drumul de cost maxim este reprezentat de nodurile: 5 -> 2 -> 1 -> 3
Pentru cea de-a doua intrebare drumul este: 4 -> 2 -> 5

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