#include #include using namespace std; struct vrchol { int cislo_vrcholu; vector sousedi; int velikost_podstromu; int p_koren_v; // Počet způsobů odebírání vrcholů z podstromu zakořeněného ve v. int p_v_v; // Počet způsobů odebírání tak, aby v byl poslední. int urci_velikost_podstromu(int z); int urci_p_koren_v(int z); void urci_p_v_v(int w); }; static int N; static vector graf; static vector fact; // Rekurzivní průchod stromem, při němž určujeme velikosti podstromů. // Do aktuálního vrcholu jsme přišli z vrcholu Z. int vrchol::urci_velikost_podstromu(int z) { vector::iterator s; velikost_podstromu = 1; for (s = sousedi.begin(); s != sousedi.end(); s++) { if (*s == z) continue; velikost_podstromu += graf[*s].urci_velikost_podstromu(cislo_vrcholu); } return velikost_podstromu; } // Rekurzivní průchod stromem, při němž určujeme počet způsobů odebírání // vrcholů z aktuálního podstromu. Do aktuálního vrcholu jsme přišli z vrcholu Z. int vrchol::urci_p_koren_v(int z) { vector::iterator s; p_koren_v = fact[velikost_podstromu - 1]; for (s = sousedi.begin(); s != sousedi.end(); s++) { if (*s == z) continue; p_koren_v /= fact[graf[*s].velikost_podstromu]; p_koren_v *= graf[*s].urci_p_koren_v(cislo_vrcholu); } return p_koren_v; } // Rekurzivní průchod stromem, při němž určujeme počet způsobů odebírání // vrcholů tak, aby aktuální vrchol byl poslední. Otec aktuálního vrcholu // je vrchol W. void vrchol::urci_p_v_v(int w) { vector::iterator s; if (w == -1) p_v_v = p_koren_v; else { p_v_v = graf[w].p_v_v * fact[velikost_podstromu]; for (s = sousedi.begin(); s != sousedi.end(); s++) { if (*s == w) continue; p_v_v /= fact[graf[*s].velikost_podstromu]; p_v_v *= graf[*s].p_koren_v; } p_v_v /= p_koren_v * (N - velikost_podstromu); } for (s = sousedi.begin(); s != sousedi.end(); s++) { if (*s == w) continue; graf[*s].urci_p_v_v(cislo_vrcholu); } } int main() { int i, f, res; scanf("%d\n", &N); graf.resize(N); for (i = 0; i < N; i++) graf[i].cislo_vrcholu = i; // Předpočítáme faktoriály. fact.push_back(1); fact.push_back(1); for (i = 2, f = 2; i < N; i++, f *= i) fact.push_back(f); // Načteme vstup. for (i = 0; i < N-1; i++) { int u, v; scanf("%d%d", &u, &v); graf[u - 1].sousedi.push_back(v - 1); graf[v - 1].sousedi.push_back(u - 1); } // Rekurzivní průchody stromem. graf[0].urci_velikost_podstromu(-1); graf[0].urci_p_koren_v(-1); graf[0].urci_p_v_v(-1); for (i = 0, res = 0; i < N; i++) res += graf[i].p_v_v; printf("%d\n", res); return 0; }