==Include(page="template/taskheader" task_id="trib")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Consiliul tribului
 
 
 
Tribul Kazooba este format din N oameni ce doresc sa se reuneasca pentru un consiliu al tribului. Oamenii sunt cu totii descendenti a unui singur om, care este seful tribului. Deoarece toti oamenii acestui trib au o viata lunga, ascendentii fiecarei persoane, chiar si seful tribului, sunt in viata si se vor prezenta la consiliu.
 
Oamenii ajung la consiliu intr-o anumita ordine si se aseaza la mese la venire. Ei stau intr-un rand de mese paralele. Prima masa este asezata la poalele Muntelui Sfant, si randul se extinde infinit spre vest (partea opusa muntelui). Pe de alta parte, fiecare om ar dori sa fie cat mai aproape de divinitate, asa ca, atunci cand soseste, el se aseaza catre masa cea mai apropiata de Muntele sfant la care nu s-a asezat nici unul dintre copii sau tatal lui.
 
Ca de obicei, zeii tribului au o inclinatie aparte pentru frumusete. Ei ar dori sa ceara membrilor tribului sa soseasca la consiliu intr-o ordine in care numarul de mese ocupate sa fie maxim. Din pacate, ei nu au nici un fel de inclinatie pentru programare, asa ca v-au cerut voua sa scrieti un program pentru asta.
 
h2. Cerinta
 
Scrieti un program care determina numarul maxim de mese ce poate fi ocupat la consiliu.
 
h2. Date de Intrare
 
Prima linie a fisierului trib.in contine un numar intreg N, reprezentand numarul de oameni din trib. Oamenii sunt numerotati de la 1 la N; seful lor este numarul 1. Fiecare dintre urmatoarele linii contin doua numere A, B cu semnificatia "exista o legatura directa de rudenie intre persoanele A si B". Relatiile descrise in fisierul de intrare sunt corecte (de exemplu nu exista cicluri, iar fiecare persoane este unul dintre descendentii sefului).
 
h2. Date de Iesire
 
Fisierul trib.out are o singura linie ce contine numarul maxim de mese care pot fi ocupate.
 
h2. Restrictii si precizari
 
&#159; 1 < N <= 100 000
 
&#159; pentru 30% dintre teste N <= 1000
 
&#159; orice masa are capacitate nelimitata
 
h2. Exemplu
 
trib.in trib.out Explicatie
5 3 Daca oamenii sosec in ordinea 2 4 1 5 3, ei se aseaza astfel:
 
1 4 -2 se aseaza la prima masa
 
3 2 -4 se aseaza la prima masa
 
1 3 -1 are un fiu (4) la prima masa asa ca se aseaza la masa a 2-a
 
3 5 -5 se aseaza la prima masa
 
-3 are 2 fii la prima masa (2 si 5) si pe tatal sau (1) la a 2-a masa, asa ca se aseaza la a 3-a masa
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/trib/enunt_files/filelist.xml

==Include(page="template/taskheader" task_id="trib")==
 
Tribul Kazooba este format din $N$ oameni ce doresc sa se reuneasca pentru un consiliu al tribului. Oamenii sunt cu totii descendenti a unui singur om, care este seful tribului. Deoarece toti oamenii acestui trib au o viata lunga, ascendentii fiecarei persoane, chiar si seful tribului, sunt in viata si se vor prezenta la consiliu.
Oamenii ajung la consiliu intr-o anumita ordine si se aseaza la mese la venire. Ei stau intr-un rand de mese paralele. Prima masa este asezata la poalele Muntelui Sfant, si randul se extinde infinit spre vest (partea opusa muntelui). Pe de alta parte, fiecare om ar dori sa fie cat mai aproape de divinitate, asa ca, atunci cand soseste, el se aseaza catre masa cea mai apropiata de Muntele sfant la care nu s-a asezat nici unul dintre copii sau tatal lui.
Ca de obicei, zeii tribului au o inclinatie aparte pentru frumusete. Ei ar dori sa ceara membrilor tribului sa soseasca la consiliu intr-o ordine in care numarul de mese ocupate sa fie maxim. Din pacate, ei nu au nici un fel de inclinatie pentru programare, asa ca v-au cerut voua sa scrieti un program pentru asta.
 
h2. Cerinta
 
Scrieti un program care determina numarul maxim de mese ce poate fi ocupat la consiliu.
 
h2. Date de Intrare
 
Prima linie a fisierului $trib.in$ contine un numar intreg $N$, reprezentand numarul de oameni din trib. Oamenii sunt numerotati de la 1 la $N$; seful lor este numarul 1. Fiecare dintre urmatoarele linii contin doua numere $A, B$ cu semnificatia "exista o legatura directa de rudenie intre persoanele $A$ si $B$". Relatiile descrise in fisierul de intrare sunt corecte (de exemplu nu exista cicluri, iar fiecare persoane este unul dintre descendentii sefului).
 
h2. Date de Iesire
 
Fisierul $trib.out$ are o singura linie ce contine numarul maxim de mese care pot fi ocupate.
 
h2. Restrictii si precizari
 
* $1 < N &le; 100 000$
* pentru $30%$ dintre teste $N &le; 1000$
* orice masa are capacitate nelimitata
 
h2. Exemplu
 
table(example). |_. trib.in |_. trib.out |
| 5
1 4
3 2
1 3
3 5 | 3 |
 
h3. Explicatie
 
Daca oamenii sosec in ordinea 2 4 1 5 3, ei se aseaza astfel:
-2 se aseaza la prima masa
-4 se aseaza la prima masa
-1 are un fiu (4) la prima masa asa ca se aseaza la masa a 2-a
-5 se aseaza la prima masa
-3 are 2 fii la prima masa (2 si 5) si pe tatal sau (1) la a 2-a masa, asa ca se aseaza la a 3-a masa
 

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