==Include(page="template/taskheader" task_id="concurs")==
 
==Include(page="template/raw")==
 
***
 
Concurs
 
 
 
Furee Pede s-a angajat la BIT (aceasta firma are structura ierarhica in forma de arbore) si a primit sarcina de a gestiona un concurs. La acest concurs participa cu proiecte echipe de cate doi angajati. Numarul de puncte acumulate de echipa este cel daruit de cel mai mic sef comun al celor doi componenti din echipa. Se cunosc echipele participante la concurs, ierarhia firmei si numarul de puncte pe care le poate darui fiecare angajat.
 
h2. Cerinta
 
Furee Pede va cere ajutorul si vrea sa afle echipa castigatoare (cea care primeste cele mai multe puncte).
 
h2. Date de Intrare
 
Prima linie a fisierului concurs.in se afla N si M, separate prin cate un spatiu. N reprezinta numarul angajatilor , iar M numarul echipelor participante la concurs. Pe urmatoarea linie se afla N numere naturale reprezentand punctele pe care le poate darui fiecare angajat. Urmatoarele N-1 linii contin cate doua numere X,Y care descriu ierarhia firmei(X este seful lui Y). In final urmeaza M linii cu cate doua numere, reprezentand numerele de ordine ale componentilor fiecarei echipe.
 
h2. Date de Iesire
 
Pe prima linie a fisierului concurs.out se va afisa trei numare, primul reprezentand punctajul echipei castigatoare , iar celelalte doua componentii echipei castigatoare.
 
h2. Restrictii si precizari
 
** 0 < N < 32001
 
** 0 < M < 500001
 
** Punctajul maxim este mai mic decat 2.000.000.000
 
** In cazul in care un component al unei echipe este seful celuilalt atunci proectul primeste puncte chiar de la acesta.
 
** In cazul in care mai multe echipe realizeaza acelasi punctaj se va afisa echipa in care numarul de ordine al primului component este mai mic,iar daca si acesta este egal se va afisa echipa in care numarul de ordine celui de-al doilea component este mai mic.
 
h2. Exemplu
 
concurs.in|concurs.out|Explicatie
 
5 2 |4 3 2 |Seful comun al lui 3 4 este 2, echipa castiga
| |4. Seful comun al lui 3 2 este 2 , echipa
6 4 2 2 2 | |castiga 4. Raspunsul este 3 2 deoarece
| |3=3,dar 2<4.
1 2 | |
| |
1 5 | |
| |
2 3 | |
| |
2 4 | |
| |
3 4 | |
| |
3 2 | |
 

==Include(page="template/taskheader" task_id="concurs")==
 
Furee Pede s-a angajat la BIT (aceasta firma are structura ierarhica in forma de arbore) si a primit sarcina de a gestiona un concurs. La acest concurs participa cu proiecte echipe de cate doi angajati. Numarul de puncte acumulate de echipa este cel daruit de cel mai mic sef comun al celor doi componenti din echipa. Se cunosc echipele participante la concurs, ierarhia firmei si numarul de puncte pe care le poate darui fiecare angajat.
 
h2. Cerinta
 
Furee Pede va cere ajutorul si vrea sa afle echipa castigatoare (cea care primeste cele mai multe puncte).
 
h2. Date de Intrare
 
Prima linie a fisierului $concurs.in$ se afla $N$ si $M$, separate prin cate un spatiu. $N$ reprezinta numarul angajatilor , iar $M$ numarul echipelor participante la concurs. Pe urmatoarea linie se afla $N$ numere naturale reprezentand punctele pe care le poate darui fiecare angajat. Urmatoarele $N-1$ linii contin cate doua numere $X,Y$ care descriu ierarhia firmei({$X$} este seful lui $Y$). In final urmeaza $M$ linii cu cate doua numere, reprezentand numerele de ordine ale componentilor fiecarei echipe.
 
h2. Date de Iesire
 
Pe prima linie a fisierului $concurs.out$ se va afisa trei numare, primul reprezentand punctajul echipei castigatoare , iar celelalte doua componentii echipei castigatoare.
 
h2. Restrictii si precizari
 
* $0 < N < 32001$
* $0 < M < 500001$
* Punctajul maxim este mai mic decat $2.000.000.000$
* In cazul in care un component al unei echipe este seful celuilalt atunci proectul primeste puncte chiar de la acesta.
* In cazul in care mai multe echipe realizeaza acelasi punctaj se va afisa echipa in care numarul de ordine al primului component este mai mic,iar daca si acesta este egal se va afisa echipa in care numarul de ordine celui de-al doilea component este mai mic.
 
h2. Exemplu
 
table(example). |_. concurs.in|_. concurs.out|
| 5 2
6 4 2 2 2
1 2
1 5
2 3
2 4
3 4
3 2 | 4 3 2 |
 
h3. Explicatie
 
Seful comun al lui 3 4 este 2, echipa castiga 4. Seful comun al lui 3 2 este 2 , echipa castiga 4. Raspunsul este 3 2 deoarece 3=3,dar 2<4.
 
==Include(page="template/taskfooter" task_id="concurs")==

==Include(page="template/taskfooter" task_id="concurs")==

396