Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-07-21 20:17:49.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:treemis.in, treemis.outSursăConcurs Mihai Patrascu 2013
AutorAdrian Budau, Andrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Treemis

Tassadar are un arbore cu N noduri numerotate de la 0 la N - 1, fiecare nod având asociată o valoare întreagă. Fiecărui lanţ îi este atribuit un şir de numere format din valorile asociate nodurilor de pe acesta, în ordinea parcurgerii lor. Un subşir crescător al unui lanţ se defineşte ca fiind un subşir crescător al şirului de valori asociat lanţului respectiv. Tassadar se întreabă care este subşirul crescător de lungime maximă al vreunui lanţ din arbore.

Date de intrare

Fişierul de intrare treemis.in conţine pe prima linie un număr întreg N cu semnificaţia din enunţ. Pe linia următoare se află N numere întregi Vi, 0 ≤ i < N, reprezentând valorile asociate nodurilor. Pe următoarele N - 1 linii se găsesc câte două numere întregi x şi y cu semnificaţia că există o muchie între nodurile x şi y.

Date de ieşire

În fişierul de ieşire treemis.out conşine un singur număr întreg, reprezentând lungimea celui mai lung subşir crescător.

Restricţii

  • 1 ≤ N ≤ 100.000
  • -1.000.000.000 ≤ Vi ≤ 1.000.000.000
  • subşirul nu trebuie să fie neapărat strict crescător

Exemplu

treemis.intreemis.out
7
1 2 9 3 -1 5 4
0 1
1 2
2 3
3 4
2 5
5 6
3

Explicaţie

Subşirul crescator maximal are lungimea 3. Unul dintre aceste subşiruri se gaseste pe lanţul de la nodul 0 la nodul 6, care are asociat şirul de valori {1, 2, 9, 5, 4}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?