Masala #VINPCDQY7C
Two Trees (Ikki daraxt)
Daraxt deb bog’langan yo’nalmagan asiklik grafga aytiladi.
Sizga ikkita ildizli daraxt berilgan, ikkala daraxtda ham N tadan tugun bor. Birinchi daraxtning ildizi , ikkinchi daraxtning ildizi -tugun.
deb shunday tugunlar to’plamiga aytiladiki, birinchi daraxtda dan u tugunga boruvchi yo’l tugundan o’tadi. Xuddi shunday, deb shunday tugunlar to’plamiga aytiladiki, ikkinchi daraxtda dan tugunga boruvchi yo’l tugundan o’tadi.
Sizdan so’ralgan narsa barcha tugunlar uchun ∩ to’plam kesishmalarining o’lchamlarini topish.
Birinchi qatorda sizga , va butun sonlari beriladi - tugunlar soni va daraxtlarning ildizlari.
Ikkinchi qatorda butun sonlari beriladi. Bunda barcha va
uchun birinchi daraxtda i va p1 [i] tugunlar o’rtasida qirra bor.
Uchinchi qatorda butun sonlari beriladi. Bunda barcha va uchun ikkinchi daraxtda va tugunlar o’rtasida qirra bor.
E’tibor bering, va elementlarning qiymatlari −1ga teng.
Chegaralar
• 2 ≤ ≤ 3 · 105
• 1 ≤ , ≤
• 1 ≤ ≤ , barcha va uchun
• , barcha va uchun
• va va massivlar daraxt hosil qilishi kafolatlanadi.
Subtasks
bu bo’ladigan indekslar soni bo’lsin.
Binar daraxt deganda barcha tugunlar uchun yoki shart bajariladigan
daraxtga aytiladi.
Chiziqli daraxt deganda barcha 1 ≤ v ≤ N tugunlar uchun c(v) ≤ 1 shart bajariladigan daraxtga
aytiladi.
1. (11 ball) Daraxtlar bir xil, ya’ni va
2. (12 ball) ≤ 3000
3. (13 ball) Ikkala daraxtlar ham binar.
4. (17 ball) Ikkala daraxtlar ham chiziqli.
5. (21 ball) Birinchi daraxt chiziqli.
6. (26 ball) Qo’shimcha chegaralarsiz.
Yagona qatorda ta son chiqaring, har bir uchun javob.
# | input.txt | output.txt |
---|---|---|
1 |
5 3 1 3 3 -1 1 2 -1 1 2 3 3 |
2 2 3 1 1 |
Masalan, = 5, = 3, = 1 bo’lsin, hamda = [3, 3, −1, 1, 2] va = [−1, 1, 2, 3, 3] deylik. Uholda daraxtlar quyidagi ko’rinishda bo’ladi:
• = {1, 4} va = {1, 2, 3, 4, 5}. Ularning kesishmasi {1, 4}ga teng.
• = {2, 5} va = {2, 3, 4, 5}. Ularning kesishmasi {2, 5}ga teng.
• = {1, 2, 3, 4, 5} va = {3, 4, 5}. Ularning kesishmasi {3, 4, 5}ga teng.
• = {4} va = {4}. Ularning kesishmasi {4}ga teng.
• = {5} va = {5}. Ularning kesishmasi {5}ga teng.