Finále

F: Rozlitá barva

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Graf je struktura sestávající z množiny vrcholů a množiny hran, kde každá hrana vede mezi dvojicí vrcholů. Typickým příkladem je dopravní síť; vrcholy jsou křižovatky a silnice mezi nimi jsou hrany. Strom je graf, ve kterém neexistují cykly a ve kterém se dá po hranách dostat mezi každými dvěma vrcholy.

Pepíček si hraje se stromem o N vrcholech. Všechny vrcholy stromu jsou na začátku bílé. Pepíček má kyblík barvy, pomocí kterého může provést následující operaci: Vybere si vrchol v a nezáporné celé číslo d. Pak obarví na černo všechny vrcholy u, které jsou od v vzdálené maximálně d hran.

Pepíčka jakožto umělce a matematika zajímá, kolik různých obarvení může jedním provedením této operace získat. Dvě obarvení jsou různá, pokud je aspoň jeden vrchol v jednom obarvení bílý a v druhém černý.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku číslo N. Následuje dalších N-1 řádků; na i-tém jsou čísla ai a bi která říkají, že mezi vrcholy ai a bi vede hrana. Vrcholy jsou číslované od 1 do N.

Tvar výstupu

Vypište jedno číslo, počet různých obarvení, které může Pepíček dostat.

Lehká verze

  • T ≤ 10
  • 2 ≤ N ≤ 500

Těžká verze

  • T ≤ 10
  • 2 ≤ N ≤ 100 000

Ukázkový vstup

1
5
1 2
1 3
1 4
4 5

Ukázkový výstup

11

Vysvětlení ukázkového vstupu a výstupu

Všech 11 dosažitelných obarvení můžete vidět na obrázku níže.

Všimněte si například, že pokud chce Pepíček obarvit všechny vrcholy kromě vrcholu 5, může to udělat třemi různými způsoby:

  • v=1, d=1
  • v=2, d=2
  • v=3, d=2
Tyto se nicméně počítají jen jednou, protože vytvoří stejné obarvení.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)