Fişierul intrare/ieşire:divizori2.in, divizori2.outSursăAlgoritmiada 2015 Runda Finala
AutorAdrian Budau, Eugenie Daniel Posdarascu, Mihai CalanceaAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test2 secLimită de memorie132768 kbytes
Scorul tăuN/ADificultateN/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.indivizori2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?