== include(page="template/taskheader" task_id="inghetare") ==
!>problema/inghetare?iceman.jpg!
În Tărâmul Ooo există $n$ aşezări, legate între ele prin $n - 1$ poteci astfel încât se poate ajunge de la orice aşezare la oricare alta folosind doar potecile respective.
Regele Gheţii, supărat că Finn şi Jake îl tot înfrâng, vrea să aducă haos în ţinut. Planul lui este simplu: va distruge potecile una câte una. În fiecare secundă, el alege aleatoriu o potecă neîngheţată şi creează pe ea un strat gros de gheaţă, astfel blocând-o. Regele se declară mulţumit doar în momentul în care nu mai există vreo aşezare cu $3$ sau mai multe poteci neîngheţate care o leagă de alte aşezări.
Determinaţi expected value la prima secundă în care regele va fi mulţumit dacă îşi desfăşoară planul.
Determinaţi expected value de prima secundă în care regele va fi mulţumit dacă îşi desfăşoară planul, modulo $10^9^+7$.
h2. Date de intrare
Fişierul de intrare $inghetare.in$ conţine:
* pe prima linie numărul $n$, reprezentând numărul de aşezări;
* pe următoarele $n-1$ linii câte două numere $u$ şi $v$, reprezentând că există o potecă între aşezările $u$ şi $v$.
Fişierul de intrare $inghetare.in$ conţine:
* Pe prima linie numărul $n$, reprezentând numărul de aşezări;
* Pe următoarele $n-1$ linii câte două numere $u$ şi $v$, reprezentând că există o potecă între aşezările $u$ şi $v$.
h2. Date de ieşire
În fişierul de ieşire $inghetare.out$ se va afişa un număr real: valoarea aşteptată căutată.
Răspunsul va fi considerat corect dacă are o eroare absolută sau relativă de cel mult $10^{-6}$.
În fişierul de ieşire $inghetare.out$ se va afişa un număr întreg între $0$ şi $10^9^+6$ inclusiv, răspunsul la problemă.
h2. Restricţii
* $1 ≤ n ≤ 2000$
* $1 ≤ n ≤ 2 000$
* $1 ≤ u, v ≤ n$
Subtaskuri:
|_. # |_. Punctaj |_. Restricţii |
| 1 | 3 | $n ≤ 10$ |
| 2 | 12| Există exact $1$ aşezare cu strict mai mult de $2$ poteci conectate la ea |
| 1 | 9 | $n ≤ 10$ |
| 2 | 16 | Există exact $1$ aşezare cu strict mai mult de $2$ poteci conectate la ea |
| 3 | 35 | $n ≤ 300$ |
| 4 | 50 | Fără alte restricţii |
| 4 | 40 | Fără alte restricţii |
h2. Exemplu
h2. Exemple
table(example).
|_. inghetare.in |_. inghetare.out |
| 5
table(example). |_. inghetare.in |_. inghetare.out |
| 2
1 2
|0
|
| 4
1 2
1 3
1 4
| 1
|
| 8
1 2
2 3
2 4
4 5
| 2.500000
1 3
1 4
2 5
2 6
2 7
3 8
| 685714294
|
h3. Explicaţie
În acest arbore, nodul $2$ are grad $3$.
Regele trebuie să îngheţe cel puţin una dintre cele $3$ muchii care pleacă din nodul $2$ pentru ca nicio aşezare să nu mai aibă grad $\geq 3$.
Se poate demonstra că valoarea aşteptată a primei secunde când condiţia se îndeplineşte este $2.5$.
Pentru primul exemplu, regele este mereu mulţumit chiar fără să îngheţe vreo potecă.
Pentru al doilea exemplu, dacă oricare din poteci este îngheţată, regele este mulţumit instant. Astfel, după 1 secundă regele mereu va fi mulţumit, deci expected value este 1.
== include(page="template/taskfooter" task_id="inghetare") ==
