Ոչ կարճ ճանապարհներ
Ինչպես բոլորդ հիշում եք, հունվարի 29-ը Հայկի ծննդյան օրն է, և նրա մեծ եղբայրը ծննդյան օրվա առթիվ Հայկին նվիրել էր
n գագաթ պարունակող գրաֆ, որն իրենից ներկայացնում էր ծառ (ծառը դա n-1 կող պարունակող կապակցված գրաֆն է)։ Քանի որ Հայկի ծննդյան օրը մոտենում է, նրա մեծ եղբայրն այս տարի իրեն առաջարկում է լուծել հետևյալ խնդիրը, իր անցած տարվա նվերի հետ կապված. Տրված է n գագաթ պարունակող ծառ և մեկ ամբողջ k թիվ։ Անհրաժեշտ է գտնել իրարից տարբեր ճանապարհների քանակը, որոնց երկարությունը մեծ է տրված k թվից։Մուտքային տվյալներ
Մուտքային տվյալների առաջին տողում տրված են երկու ամբողջ թվեր՝ ծառի գագաթների քանակը
n և խնդրում նկարագրված k ամբողջ թիվը։ Հաջորդ n-1 տողերից յուրաքանչյուրում տրված են երկու ամբողջ թվեր` v u (1 ≤ u ≠ v ≤ n), որը նշանակում է, որ v գագաթը միացված է u գագաթին կողով։Ելքային տվյալներ
Արտածեք մեկ ամբողջ թիվ՝ իրարից տարբեր ճանապարհների քանակը, որոնց երկարությունը մեծ է
k թվից։Օրինակ
Մուտք | Ելք |
5 2
1 2
2 3
3 4
4 5 | 3 |
6 1
1 2
1 3
1 6
3 4
3 5 | 10 |
Բացատրություն
Առաջին օրինակում,
2-ից մեծ երկարություն ունեցող ճանապարհների քանակը հավասար է 3-ի (1 -> 4, 1 -> 5, 2 -> 5)։Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (5 միավոր)
, տրված ծառը իրենից ներկայացնում է աստղ` բոլոր գագաթները միացած են1համարով գագաթին,
- Ենթախնդիր 2 (7 միավոր)
- Ենթախնդիր 3 (9 միավոր)
, տրված ծառը իրենից ներկայացնում է շղթա, այսինքն գրաֆիiրդ կողը միացնում էiրդ գագաթըi+1րդի հետ,
- Ենթախնդիր 4 (10 միավոր)
- Ենթախնդիր 5 (19 միավոր)
- Ենթախնդիր 6 (50 միավոր)
Constraints
Time limit: 5 seconds
Memory limit: 1000 MB
Output limit: 1 MB