| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
NOSHORTP - Ոչ կարճ ճանապարհներ |
Շարադրանք
Ինչպես բոլորդ հիշում եք, հունվարի 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)։
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2023-02-05 |
| Ժամանակի սահմանափակումը. | 0.300s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Մարզային փուլ, 2022-23 |
թաքցնել մեկնաբանությունները
|
2023-12-08 23:18:25
n <= 10^5, k <= 20 |
|
|
2023-12-08 23:18:25
Վերջին խմբագրածը. 2023-12-08 23:18:43 |
|
|
2023-12-08 23:18:22
Վերջին խմբագրածը. 2023-12-08 23:18:37 |
RSS