Masala G
Kubok yo'li
Nihoyat, "1 Yil Kubogi" kuni keldi. Auditoriyadagi katta doskaga akademiyaning bir yillik yo'li daraxt ko'rinishida chizildi: bir joyda birinchi dars, bir joyda ichki duel, boshqa joyda tahlildan keyingi upsolve, yana bir joyda xalqaro medalga olib borgan mashqlar.
Har bir tugun bitta shunday lahzani bildiradi. Daraxt \(1\)-tugundan ildizlangan. Agar \(u\) tugun \(v\) tugunning ajdodi bo'lsa yoki \(u = v\) bo'lsa, \(u\) dan \(v\) gacha daraxt bo'ylab olingan yo'l o'quv yo'li deyiladi. Demak, bitta tugunning o'zi ham o'quv yo'li hisoblanadi.
Akademiyada \(m\) ta asosiy ko'nikma ajratilgan. Ularni \(0\) dan \(m-1\) gacha raqamlaymiz. Har bir tugunga \(x_i\) soni yozilgan. Bu sonning ikkilik yozuvi \(m\) ta ko'nikma haqida ma'lumot beradi: agar ikkilik yozuvdagi \(j\)-o'rin \(1\) bo'lsa, shu lahzada \(j\)-ko'nikma ishlatilgan; \(0\) bo'lsa, ishlatilmagan. O'rinlar o'ngdan chapga qarab \(0\) dan sanaladi. Bunday sonni ko'nikma kodi deb ataymiz.
Masalan, \(m=3\) bo'lsa, \(5\) soni ikkilikda \(101\). Bu \(0\)- va \(2\)-ko'nikmalar ishlatilganini, \(1\)-ko'nikma ishlatilmaganini bildiradi.
Bir nechta ko'nikma kodini birlashtirish quyidagicha bajariladi: har bir ko'nikma tanlangan kodlar ichida toq marta uchrasa, natijada shu o'rin \(1\), juft marta uchrasa \(0\) bo'ladi. Bu amal odatda XOR deb ataladi.
O'quv yo'lidagi istalgan tugunlar to'plamini (bo'sh to'plamni ham) tanlab, ularning ko'nikma kodlarini shu usulda birlashtirish mumkin. Bo'sh to'plam tanlansa, natija \(0\) bo'ladi.
O'quv yo'li to'liq deyiladi, agar shu yo'ldagi tugunlardan foydalanib \(0\) dan \(2^m - 1\) gacha bo'lgan barcha ko'nikma kodlarini hosil qilish mumkin bo'lsa.
To'liq o'quv yo'llari sonini toping.
Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 1 \le m \le 20)\).
Ikkinchi qatorda \(n\) ta butun son \(x_1, x_2, \ldots, x_n\) beriladi \((0 \le x_i < 2^m)\). Bu sonlar tugunlardagi ko'nikma kodlari.
Keyingi \(n-1\) qatorda daraxt qirralari beriladi. Har bir qatorda ikkitadan butun son \(u\) va \(v\) yoziladi \((1 \le u,v \le n,\ u \ne v)\).
To'liq o'quv yo'llari sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 2 1 2 3 1 2 2 3 |
3 |
| 2 |
3 2 0 1 2 1 2 1 3 |
0 |
| 3 |
3 1 0 1 1 1 2 1 3 |
4 |
Birinchi namunada \(m=2\), demak barcha kodlar \(0, 1, 2, 3\) bo'lishi kerak. \(1 \to 2\) yo'lida kodlar \(1\) va \(2\): hech narsa tanlanmasa \(0\), faqat \(1\) tanlansa \(1\), faqat \(2\) tanlansa \(2\), ikkalasi tanlansa \(3\) hosil bo'ladi. Demak, bu yo'l to'liq. Xuddi shunday, \(1 \to 2 \to 3\) va \(2 \to 3\) yo'llari ham to'liq. Jami \(3\) ta.
Ikkinchi namunada \(1 \to 2\) yo'lidagi kodlardan faqat \(0\) va \(1\) ni, \(1 \to 3\) yo'lidagi kodlardan esa faqat \(0\) va \(2\) ni hosil qilish mumkin. To'liq yo'l yo'q.
Uchinchi namunada \(m=1\), kerakli kodlar \(0\) va \(1\). \(2\)- yoki \(3\)-tugunni o'z ichiga olgan har bir o'quv yo'lida \(1\) kodi bor, shuning uchun ularning har biri to'liq: \(1 \to 2\), \(2\), \(1 \to 3\), \(3\). Jami \(4\) ta.
Telegram kanalimizga obuna bo'ling