Problem description

Back
Show PDF
Andrzej Hood
(B)
Limit pamięci: 128 MB
Limit czasu: 5.00 s

Andrzej Hood z Bytewood jest bohaterem znanym w całej Bajtocji. Żyje on wyłącznie po to, by redystrybuować dobra przekazując je z rąk ludzi bogatych do rąk ludzi biednych. Jak już wspomniałem, zamieszkuje on las Bytewood, który składa się z polanek i dróżek leśnych między nimi. Z każdej polanki a można dojść do każdej polanki b na dokładnie jeden sposób.1

Na każdej dróżce czai się banda Andrzeja Hooda, gotowa, by redystrybuować. Oto jak działa jej system:

  • Każda dróżka ma przypisany zbiór towarów, na jakie dana banda poluje (towary będą oznaczane liczbami naturalnymi od 1 do 64).
  • Jeśli podróżny przechodzący przez dróżkę posiada towar należący do przypisanego jej zbioru, to zostaje on zabrany przez bandę.
  • Jeśli podróżny nie posiada towaru należącego do przypisanego jej zbioru, banda wręcza mu go w prezencie.2

Bogaci kupcy zauważyli, że w tym systemie istnieją szczególne, bezpieczne szlaki,3 które finalnie nie zmieniają ekwipunku podróżnych, niezależnie od tego, z czym wyruszają. Innymi słowy, na takich szlakach, bandy zabierają każdy towar dokładnie tyle samo razy, ile razy go dają.

Twoim zadaniem jest napisać program, który wyznaczy liczbę wszystkich bezpiecznych szlaków.

Dwa szlaki uznajemy za różne, jeśli istnieje przynajmniej jedna dróżka, która wchodzi w skład pierwszego i nie wchodzi w skład drugiego. W szczególności, dla dowolnych a, b, szlak łączący polany o numerach a i b jest tożsamy ze szlakiem łączacym polany o numerach b i a.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę polanek.

W kolejnych N − 1 wierszach wejścia znajduje się opis dróżek.

Na początku i-tego z nich znajdują się trzy liczby naturalne 1 ≤ ai, bi ≤ N, 0 ≤ ki ≤ 64, oddzielone pojedynczymi odstępami. Oznaczają one, że istnieje dróżka łącząca polanki o numerach ai i bi, do której przypisany jest zbiór mający ki elementów.

Po nich znajduje się ki różnych, dodatnich liczb naturalnych, nie większych niż 64, pooddzielanych pojedynczymi odstępami. Liczby te są elementami zbioru przypisanego do i-tej dróżki.

Wyjście

W pierwszym i jedy­nym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą liczbę bezpiecznych szlaków.

Ograniczenia

2 ≤ N ≤ 500 000
0 ≤ ki ≤ 64

Przykład

Wejście Wyjście Wyjaśnienie 
6
1 2 1 2
2 3 1 1
2 4 0
2 5 1 1
1 6 2 1 2

4

W wersji HTML poniżej znajduje się grafika obrazująca test przykładowy.
Jedyne bezpieczne szlaki łączą polanki o numerach: (3, 6), (2, 4), (3, 5), oraz (5, 6).

  1. Właściwie to Bytewood jest drzewem, ale ludzie nie żyją na drzewach.↩︎

  2. Wszystkie bandy mają nieskończone ilości każdego towaru i mogą go bezkarnie rozdawać.↩︎

  3. Szlak to po prostu ścieżka, nie mylić z dróżką.↩︎