Fişierul intrare/ieşire:arbore7.in, arbore7.outSursăONI 2016, clasele 11-12
AutorDenis-Gabriel MitaAdăugată deAndrei1998Constantinescu Andrei-Costin Andrei1998
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arbore7

Se dă un arbore (graf conex aciclic) cu N noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim. Aflaţi care este numărul maxim de componente conexe pe care le putem obţine şi câte submulţimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe.

Date de intrare

Pe prima linie a fişierului de intrare arbore7.in se va afla numărul natural N, reprezentând numărul de noduri ale arborelui. Pe următoarele N-1 linii se vor afla câte două numere X şi Y, cu semnificaţia că există o muchie între nodurile X şi Y.

Date de ieşire

Pe prima linie a fişierului de ieşire arbore7.out se vor afişa două numere naturale reprezentând numărul maxim de componente conexe pe care îl putem obţine, respectiv numărul de moduri în care putem obţine acest număr de componente conexe modulo 109+7 (adică restul împărţirii acestui număr la 1 000 000 007).

Restricţii

  • 1 ≤ N ≤ 100 000
  • Se acordă 40% din punctajul unui test dacă numărul maxim de componente conexe este corect.
  • Se acordă 60% din punctajul unui test dacă numărul de moduri este corect.
  • Pentru 20% din teste N ≤ 20
  • Pentru alte 30% din teste N ≤ 1000

Exemplu

arbore7.inarbore7.out
6
1 2
1 3
1 4
4 5
4 6
4 1
4
1 2
2 3
3 4
2 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?