Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | avd.in, avd.out | Sursă | Happy Coding 2006 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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 = n1 + n2 + ... + nk nodurile arborelui se pot imparti in k multimi astfel incat multimea i are ni noduri si fiecare multime ramane conexa, ni ≤ nj 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.
Cerinta
Dandu-se un arbore cu N noduri, calculati gradul AVD al acestuia.
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.
Date de Iesire
In fisierul avd.out vor exista T linii fiecare continand gradul AVD al arborelui descris la testului respectiv.
Restrictii si precizari
- 1 ≤ N ≤ 13
- 1 ≤ T ≤ 50
- rezultatul se va afisa cu 5 zecimale (prin rotunjire)
Exemplu
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 |
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.