| Fişierul intrare/ieşire: | divizori2.in, divizori2.out | Sursă | Algoritmiada 2015 Runda Finala |
| Autor | Adrian Budau, Eugenie Daniel Posdarascu, Mihai Calancea | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 1 sec | Limită de memorie | 132768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Divizori2
Fie A şi B doi arbori neorientaţi. Definim suma A + B ca fiind mulţimea tuturor arborilor neorientaţi care se pot obţine prin conectarea arborilor A şi B printr-o singură muchie, între oricare nod din A şi din B. Similar, definim produsul dintre un scalar K si un arbore A ca fiind K * A = A + A + ... A de K ori. Spunem că un arbore A divide un arbore B, dacă există un număr natural nenul K astfel încât B este inclus în mulţimea K * A. Observăm că asemănător cu divizibilitatea în cazul numerelor naturale, orice arbore se divide măcar cu el însuşi şi cu "unitatea", i.e arborele format dintr-un singur nod.
Dându-se un arbore T se cere să se numere câţi arbori distincti îi sunt divizori.
Date de intrare
Fişierul de intrare divizori2.in va conţine pe prima sa linie numărul N. Pe următoarele N - 1 linii se vor afla muchiile arborelui T, perechi de forma x y.
Date de ieşire
În fişierul de ieşire divizori2.out se va afla un singur număr: numărul de divizori ai lui T.
Restricţii
- 1 ≤ N ≤ 100.000
- Pentru 50% din punctaj N ≤ 5.000
- Doi arbori se considera distincti daca nu sunt izomorfi, altfel spus daca fie nu au acelasi numar de noduri sau daca nu exista o renumerotare a nodurilor din primul astfel incat sa se obtina al doilea.
Exemplu
| divizori2.in | divizori2.out |
|---|---|
| 8 2 1 3 1 4 1 6 5 7 5 8 5 1 5 | 3 |
Explicaţie
Cei 3 arbori sunt: arborele cu un singur nod, arborele din input şi graful "stea" format din 4 noduri.
