Binarno Stablo i Putevi


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++, Haskell, PyPy, Python

Dano je binarno stablo od \(n\) vrhova ukorijenjeno u vrhu \(1\) te je dan broj \(k\). Vaš zadatak je izračunati broj puteva duljine točcno \(k\) koji prolaze kroz vrh \(1\). Duljina puta između vrhova \(u\) i \(v\) je broj bridova na tom putu. Puteve od \(u\) do \(v\) i od \(v\) do \(u\) brojimo kao jedan put. Budući da broj puteva može biti jako velik, molimo vas da ispišete traženi broj modulo \(10^9 + 7\).

Ulaz

U prvom retku su dana dva broja \(n\) i \(k\), \((1 \leq k \leq n \leq 10^5)\). U sljedećih \(n-1\) redaka se nalaze parovi \(u_i\) i \(v_i\), \((1 \leq u_i, v_i \leq n)\), što znači da postoji brid između \(u_i\) i \(v_i\) u binarnom stablu. Uvijek će vam biti dano valjano binarno stablo.

Izlaz

U jedini redak ispišite jedan broj, broj puteva duljine točno \(k\) koji u sebi imaju vrh \(1\). Taj broj puteva ispišite modulo \(10^9 + 7\). U \(20%\) primjera će vrijediti \(1 \leq n \leq 300\), U \(50%\) primjera će vrijediti \(1 \leq n \leq 1000\).

Primjer ulaza

4 2
1 2
1 3
3 4

Primjer izlaza

2
Pojašnjenje

Stablo je oblika

    1
   / \
  2   3
     /
    4

i putevi duljine dva koji prolaze kroz vrh 1 su 2-1-3 i 1-3-4. Ne brojimo 3-1-2 jer je on jednak putu 2-1-3 i ne brojimo 4-3-1 jer je on jednak putu 1-3-4.

Primjer ulaza

7 4
1 2
2 3
2 5
1 4
4 6
4 7

Primjer izlaza

4
Pojašnjenje

Stablo je oblika

     1
   /   \
  2     4
 / \   / \
3   5 6   7

i putevi su 3-2-1-4-6, 3-2-1-4-7, 5-2-1-4-6 i 5-2-1-4-7.

Primjer ulaza

7 3
1 2
2 3
2 5
5 6
5 7
3 4

Primjer izlaza

3
Pojašnjenje

Stablo je oblika

      1
     /
    2
   / \
  3   5
 /   / \
4   6   7

i putevi su 1-2-3-4, 1-2-5-6 i 1-2-5-7.


Comments

There are no comments at the moment.