Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-11-08 20:45:04.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:avd.in, avd.outSursăHappy Coding 2006
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inavd.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content