Գագաթների գեղեցիկ ենթաբազմությունը
Տրված է
n գագաթանի ծառ։ Ծառի գագաթների ենթաբազմությունը կոչվում է k-գեղեցիկ, եթե ծառի յուրաքանչյուր v գագաթի համար գոյություն ունի u գագաթ այդ ենթաբազմությունից, որ v և u գագաթների հեռավորությունը չի գերազանցում k-ն։ Տրված k-ի համար ծառի k-գեղեցիկ ենթաբազմության մինիմալ հնարավոր գագաթների քանակը նշանակենք f(k)-ով։ Տրված է նաև t ամբողջ թիվը 0 ≤ t ≤ n։ Եթե t > 0, ապա անհրաժեշտ է արտածել f(t)-ն։ Հակառակ դեպքում, անհրաժեշտ է արտածել f(1) f(2) f(3) ... f(n) արժեքները։Մուտքային տվյալներ
Առաջին տողում տրված է երկու բնական թիվ՝
n և t (1 ≤ n ≤ 35000, 0 ≤ t ≤ n)։ Հաջորդ n - 1 տողերից ամեն մեկում տրված է 2 բնական թիվ՝ x, y (1 ≤ x ≠ y ≤ n)։Ելքային տվյալներ
t > 0 դեպքում ելքի միակ տողում պետք է արտածել f(t)-ն։ t = 0 դեպքում ելքի միակ տողում պետք է արտածել f(1) f(2) ... f(n) արժեքները՝ անջատված մեկական բացատանիշով։Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները:
- Ենթախնդիր 1 (7 միավոր)
1 ≤ n ≤ 15:
- Ենթախնդիր 2 (15 միավոր)
1 ≤ n ≤ 100:
- Ենթախնդիր 3 (10 միավոր)
1 ≤ n ≤ 35000, Տրված ծառը հանդիսանում է շղթա:
- Ենթախնդիր 4 (12 միավոր)
1 ≤ n ≤ 35000, k = 1:
- Ենթախնդիր 5 (21 միավոր)
1 ≤ n ≤ 35000, k ≠ 0:
- Ենթախնդիր 6 (35 միավոր) Հավելյալ սահմանափակումներ չկան։
Օրինակ
Մուտք | Ելք |
9 1
1 2
2 3
3 4
4 5
5 6
6 7
4 8
8 9 | 3 |
6 0
1 2
2 3
3 4
1 5
5 6 | 2 2 1 1 1 1 |
Բացատրություն
Առաջին օրինակում գագաթների գեղեցիկ
1-ենթաբազմության օրինակ է {2, 6, 8}-ը։Աղբյուրը՝ Հանրապետական 2022
Constraints
Time limit: 0.4 seconds
Memory limit: 512 MB
Output limit: 1 MB