== include(page="template/taskheader" task_id="tricolor") ==
Tanaka are un arbore (un tri) cu N noduri numerotate de la 1 la N. El vrea să coloreze nodurile arborelui în alb sau negru astfel încât numărul de perechi (neordonate) de noduri înfrățite să fie maxim. Două noduri sunt înfrățite dacă și numai dacă ambele sunt albe și fie sunt legate direct printr-o muchie, fie lanțul elementar unic dintre ele conține doar noduri negre.
Tanaka are un arbore (un tri) cu $N$ noduri numerotate de la $1$ la $N$. El vrea să coloreze nodurile arborelui în alb sau negru astfel încât numărul de perechi (neordonate) de noduri înfrățite să fie maxim. Două noduri sunt înfrățite dacă și numai dacă ambele sunt albe și fie sunt legate direct printr-o muchie, fie lanțul elementar unic dintre ele conține doar noduri negre.
h2. Cerinţă
Dându-se un arbore cu N noduri, să se afle numărul maxim de perechi de noduri înfrățite ale sale
care se poate obține.
Dându-se un arbore cu $N$ noduri, să se afle numărul maxim de perechi de noduri înfrățite ale sale care se poate obține.
h2. Date de intrare
Fișierul de intrare tricolor.in va conține pe primul rând un număr natural nenul T ce reprezintă numărul de teste. Urmează T teste, fiecare test va descrie un arbore pentru care trebuie să se rezolve
cerința. Pe primul rând al unui test apare un număr natural N ce reprezintă numărul de noduri ale arborelui din testul respectiv. Pe următoarele N-1 rânduri vor apărea câte o pereche de numere întregi x y separate printr-un spațiu, care indică existența unei muchii între nodul x și nodul y.
Fișierul de intrare $tricolor.in$ va conține pe primul rând un număr natural nenul $T$ ce reprezintă numărul de teste. Urmează $T$ teste, fiecare test va descrie un arbore pentru care trebuie să se rezolve cerința. Pe primul rând al unui test apare un număr natural $N$ ce reprezintă numărul de noduri ale arborelui din testul respectiv. Pe următoarele $N-1$ rânduri vor apărea câte o pereche de numere întregi $x y$ separate printr-un spațiu, care indică existența unei muchii între nodul $x$ și nodul $y$.
h2. Date de iesire
Fișierul de ieșire tricolor.out va conține T rânduri. Fiecare rând va conține soluția pentru câte un
test, în aceeași ordine ca în fișierul de intrare.
Fișierul de ieșire $tricolor.out$ va conține $T$ rânduri. Fiecare rând va conține soluția pentru câte un test, în aceeași ordine ca în fișierul de intrare.
h2. Restricţii și precizări
* $1 ≤ T ≤10$
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 5000$
* Într-un test oarecare, $1 ≤ x,y ≤ N, x &neq; y$
* Pentru 5 puncte, T=1 și N ≤ 15
* Pentru alte 10 puncte, T=1 și N ≤ 20
* Pentru alte 5 puncte, toți arborii descriși au exact 2 frunze și N ≤ 500
* Pentru alte 10 puncte, pentru toți arborii descriși există exact două noduri ale arborelui de care se leagă toate frunzele, situate la capetele unui lanț elementar și N ≤ 500.
* Pentru alte 50 de puncte, N ≤ 500
* Pentru alte 20 de puncte, nu există restricții suplimentare.
* Într-un test oarecare, $1 ≤ x,y ≤ N, x ≠ y$
* Pentru $5$ puncte, $T = 1$ și $N ≤ 15$
* Pentru alte $10$ puncte, $T = 1$ și $N ≤ 20$
* Pentru alte $5$ puncte, toți arborii descriși au exact $2$ frunze și $N ≤ 500$
* Pentru alte $10$ puncte, pentru toți arborii descriși există exact două noduri ale arborelui de care se leagă toate frunzele, situate la capetele unui lanț elementar și $N ≤ 500$.
* Pentru alte $50$ de puncte, $N ≤ 500$
* Pentru alte $20$ de puncte, nu există restricții suplimentare.
h2. Exemple
table(example). |_. tricolor.in |_. tricolor.out |
| 2
8 12 23 24 45 56 67 68 2 12
| 7 1
8
1 2
2 3
2 4
4 5
5 6
6 7
6 8
2
1 2
| 7
1
|
h2. Explicatie
Este optim sa coloram, in primul exemplu, astfel:
!problema/tricolor?b.png!
Ce duce la 7 perechi de noduri înfrățite.
== include(page="template/taskfooter" task_id="tricolor") ==
