Yenə ağacda AND#13124

Yenə ağacda AND

5 saniyə
256 meqabayt

Mənfi olmayan tam ədədinin ikilik yazılışındakı vahid bitlərin sayını ilə işarə edək.

təpəli ağac və tam ədədi verilib. Hər bir təpəsi üçün aşağıdakı məsələni nəzərdən keçirin.

təpəsi ağacın köküdür. Ona 2^m-1 ədədi, digər hər bir təpəyə isə -dən 2^m-1-ə qədər tam ədəd mənimsədilir. kökdən təpəsinə gedən yoldakı ədədlərin, yolun hər iki ucu daxil olmaqla, bitlər üzrə AND-i olsun.

Bütün kökdən fərqli təpələri üçün \operatorname{popcount}(\operatorname{AND}(v)) eynidirsə, yerləşdirmə cəlbedici adlanır. Hər bir mümkün kök üçün cəlbedici yerləşdirmələrin sayını moduluna görə tapın.

n=1 olduqda yeganə yerləşdirmə cəlbedici hesab olunur.

Giriş

Birinci sətirdə testlərin sayını bildirən tam ədədi (1\le t\le10^4) verilir.

Hər testin birinci sətrində iki tam və ədədi (1\le n,m\le10^5) verilir.

Növbəti n-1 sətrin hər birində tilin uclarını bildirən iki tam və ədədi (1\le u,v\le n) verilir. Verilmiş tillərin ağac əmələ gətirdiyinə zəmanət verilir.

Bütün testlər üzrə -lərin cəmi 10^5-i keçmir. -lərin cəmi də 10^5-i keçmir.

Çıxış

Hər test üçün bir sətirdə tam ədəd çap edin. -ci ədəd kökü təpəsində olan cəlbedici yerləşdirmələrin moduluna görə sayına bərabər olmalıdır.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Nümunə 3

Loading
Loading

Qeyd

Birinci nümunənin birinci testində ağacın bir təpəsi var, buna görə cavab -dir.

Birinci nümunənin ikinci testində kökə ədədi mənimsədilir. Digər təpəyə , və ya mənimsətmək olar, buna görə hər iki kök üçün cavab -dür.

Bal hesablama

  1. Alt tapşırıq ( bal): t\le10, n,m\le5.

  2. Alt tapşırıq ( bal): n,m\le20.

  3. Alt tapşırıq ( bal): hər təpənin dərəcəsi ən çox -dir.

  4. Alt tapşırıq ( bal): ağac ulduzdur, yəni bütün digər təpələrlə qonşu olan təpə var.

  5. Alt tapşırıq ( bal): n,m\le1000, \sum n\le5000, \sum m\le5000.

  6. Alt tapşırıq ( bal): əlavə məhdudiyyət yoxdur.