Masala #5LYHVFEHJD
Kanji for king (王)
N tugunli daraxt bor. Tugunlar 1 dan N gacha raqamlangan. Daraxtning nechta har xil sub-daraxti(bir yoki bir nechta qo’shni tugunlardan tashkil topgan qismi)ni "Kanji for King" daraxti shaklida ifodalash mumkinligini aniqlang!
Kanji for king daraxti:
Agar bitta sub-daraxtda qaysidir tugun mavjud bo'lsa, lekin boshqa sub-daraxtda bo'lmasa, ikkita sub-daraxt har xil hisoblanadi.
Daraxt - sikl mavjud bo'lmagan va bir tugundan boshqasiga har doim yo'l mavjud bo'lgan graf.
Kirish faylining 1-qatorida \(N(1 \le N \le 10^5)\) - tugunlar soni kiritiladi. Keyingi N-1 ta qatorning har biri ikkita butun son - \(u\) va \(v\) \((1 \le u , v \le N, u \ne v\) kiritiladi - bu degani \(u\) va \(v\) tugunlar o'zaro bog'langan.
Daraxtning nechta har xil sub-daraxtini "Kanji for King" daraxti shaklida ifodalash mumkinligini aniqlang, hamda uni \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
9 1 2 2 3 4 5 5 6 7 8 8 9 2 5 5 8 |
1 |
| 2 |
17 1 2 2 3 4 5 5 6 7 8 8 9 2 5 5 8 10 11 11 12 13 9 9 14 15 16 16 17 11 9 9 16 |
10 |
1-test uchun daraxt ko'rinishi:
Ushbu daraxtda faqatgina 1 ta Kanji for king daraxti mavjud.
2-test uchun quyidagi tugunlar Kanji for king daraxti bo'la oladi:
- 1, 2, 3, 4, 5, 6, 7, 8, 9
- 10, 11, 12, 13, 9, 14, 15, 16, 17
- 10, 11, 12, 8, 9, 14, 15, 16, 17
- 10, 11, 12, 8, 9, 13, 15, 16, 17
- 10, 11, 12, 13, 9, 14, 7, 8, 5
- 10, 11, 12, 13, 9, 16, 7, 8, 5
- 10, 11, 12, 14, 9, 16, 7, 8, 5
- 7, 8, 5, 11, 9, 13, 15, 16, 17
- 7, 8, 5, 11, 9, 14, 15, 16, 17
- 7, 8, 5, 13, 9, 14, 15, 16, 17
Telegram kanalimizga obuna bo'ling