==Include(page="template/taskheader" task_id="avd")==
 
==Include(page="template/raw")==
 
AVD
 
 
 
Un arbore este un graf neorientat, conex cu N noduri si N-1 muchii. Se numeste arbore AVD un arbore care pentru fiecare partitie a lui N=n[1]+n[2]+...+n[k] nodurile arborelui se pot imparti in k multimi astfel incat multimea i are n[i] noduri si fiecare multime ramane conexa, n[i] <= n[j] pentru i < j . Gradul AVD al unui arbore este numarul de partitii care indeplinesc conditiile anterioare impartit la numarul total de partitii existente pentru N.
 
h2. Cerinta
 
Dandu-se un arbore cu N noduri, calculati gradul AVD al acestuia.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare avd.in contine T, numarul de teste din fisier apoi vor urma cele T teste. Pe prima linie a fiecarui test se afla N numarul de noduri, urmand apoi N-1 linii continand cate doua numere x, y cu semnificatia exista muchie intre nodurile x si y.
 
h2. Date de Iesire
 
In fisierul avd.out vor exista T linii fiecare continand gradul AVD al arborelui descris la testului respectiv.
 
h2. Restrictii si precizari
 
. 1 <= N <= 13
 
. 1 <= T <= 50
 
. rezultatul se va afisa cu 5 zecimale (prin rotunjire)
 
h2. Exemplu
 
 
|avd.in |avd.out |
 
|3 |0.80000 |
|4 |1.00000 |
|1 2 |1.00000 |
|1 3 | |
|1 4 | |
|5 | |
|1 2 | |
|2 3 | |
|3 4 | |
|4 5 | |
|1 | |
 
 

==Include(page="template/taskheader" task_id="avd")==
 
Un arbore este un graf neorientat, conex cu $N$ noduri si $N-1$ muchii. Se numeste arbore AVD un arbore care pentru fiecare partitie a lui $N  = n{~1~} + n{~2~} + ... + n{~k~}$ nodurile arborelui se pot imparti in $k$ multimi astfel incat multimea $i$ are n{~i~} noduri si fiecare multime ramane conexa, $n{~i~} &le; n{~j~}$ pentru $i < j$. Gradul AVD al unui arbore este numarul de partitii care indeplinesc conditiile anterioare impartit la numarul total de partitii existente pentru $N$.
 
h2. Cerinta
 
Dandu-se un arbore cu $N$ noduri, calculati gradul AVD al acestuia.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare $avd.in$ contine $T$, numarul de teste din fisier apoi vor urma cele $T$ teste. Pe prima linie a fiecarui test se afla $N$ numarul de noduri, urmand apoi $N-1$ linii continand cate doua numere $x, y$ cu semnificatia exista muchie intre nodurile $x$ si $y$.
 
h2. Date de Iesire
 
In fisierul $avd.out$ vor exista $T$ linii fiecare continand gradul AVD al arborelui descris la testului respectiv.
 
h2. Restrictii si precizari
 
* $1 &le; N &le; 13$
* $1 &le; T &le; 50$
* rezultatul se va afisa cu $5$ zecimale (prin rotunjire)
 
h2. Exemplu
 
table(example). |_. avd.in |_. avd.out |
| 3
4
1 2
1 3
1 4
5
1 2
2 3
3 4
4 5
1
| 0.80000
1.00000
1.00000 |
 
h3. Explicatii
 
Pentru primul test, exista in total $5$ partitii pentru $4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4$ din care doar partitia $2+2$ nu poate fi obtinuta. Deci gradul AVD al arborelui este $4/5=0.80000$.
 
==Include(page="template/taskfooter" task_id="avd")==

Explicatii
Pentru primul test, exista in total 5 partitii pentru 4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4 din care doar partitia 2+2 nu poate fi obtinuta. Deci gradul AVD al arborelui este 4/5=0.80000.
==Include(page="template/taskfooter" task_id="avd")==

1310