Masala #VINPCDQY7C

Xotira 512 MB Vaqt 1000 ms
14

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 r1r_1 , ikkinchi daraxtning ildizi r2r_2 -tugun.
S1(v)S_1(v)deb shunday uu tugunlar to’plamiga aytiladiki, birinchi daraxtda r1r_1 dan u tugunga boruvchi yo’l vvtugundan o’tadi. Xuddi shunday, S2(v)S_2(v) deb shunday uu tugunlar to’plamiga aytiladiki, ikkinchi daraxtda r2r_2dan uu tugunga boruvchi yo’l vv tugundan o’tadi.
Sizdan so’ralgan narsa barcha 1vN1 ≤ v ≤ N tugunlar uchun S1(v)S_1(v) ∩ S2(v)S_2(v) to’plam kesishmalarining o’lchamlarini topish.


Kiruvchi ma'lumotlar:

Birinchi qatorda sizga NN , r1r_1 va r2r_2 butun sonlari beriladi - tugunlar soni va daraxtlarning ildizlari.
Ikkinchi qatorda p1[1],p1[2],...,p1[N]p_1[1], p_1[2],...,p_1[N] butun sonlari beriladi. Bunda barcha 1iN1 ≤ i ≤ N va ir1 i ≠ r1
uchun birinchi daraxtda i va p1 [i] tugunlar o’rtasida qirra bor.
Uchinchi qatorda p2[1],p2[2],...p2[N]p_2[1], p_2[2],...p_2[N] butun sonlari beriladi. Bunda barcha 1iN1 ≤ i ≤ N va ir2i ≠ r2 uchun ikkinchi daraxtda ii va p2[i]p_2[i]tugunlar o’rtasida qirra bor.
E’tibor bering, p1[r1]p_1[r_1] va p2[r2]p_2[r_2] elementlarning qiymatlari −1ga teng.

Chegaralar
      • 2 ≤ NN ≤ 3 · 105
      • 1 ≤ r1r_1 , r2r_2 ≤ NN
      • 1 ≤ p1[i]p_1[i] ≤ NN , barcha 1iN1 ≤ i ≤ N va ir1i≠r_1 uchun
      • 1p2[i]N1 ≤ p_2 [i] ≤ N , barcha 1iN1 ≤ i ≤ N va ir2i≠r_2 uchun
      • p1[r1]=1p_1 [r_1 ] = −1 va p2[r2]=1p_2 [r_2 ] = −1  p1p_1 va p2p_2 massivlar daraxt hosil qilishi kafolatlanadi.

Subtasks
c(v)c(v) bu p[i]=vp[i] = v bo’ladigan ii indekslar soni bo’lsin.
Binar daraxt deganda barcha 1vN1 ≤ v ≤ N tugunlar uchun c(v)=0c(v) = 0 yoki c(v)=2c(v) = 2 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 r1=r2r_1 = r_2 va p1=p2p_1 = p_2
        2. (12 ball) NN ≤ 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.


Chiquvchi ma'lumotlar:

Yagona qatorda NN ta son chiqaring, har bir vv uchun javob.


Misollar
# input.txt output.txt
1
5 3 1
3 3 -1 1 2
-1 1 2 3 3
2 2 3 1 1
Izoh:

Masalan, NN = 5, r1r_1 = 3, r2r_2 = 1 bo’lsin, hamda p2p_2 = [3, 3, −1, 1, 2] va p2p_2 = [−1, 1, 2, 3, 3] deylik. Uholda daraxtlar quyidagi ko’rinishda bo’ladi:
      • S1(1)S_1 (1) = {1, 4} va S2(1)S_2 (1) = {1, 2, 3, 4, 5}. Ularning kesishmasi {1, 4}ga teng.
      • S1(2)S_1 (2) = {2, 5} va S2(2)S_2 (2) = {2, 3, 4, 5}. Ularning kesishmasi {2, 5}ga teng.
      • S1(3)S_1 (3) = {1, 2, 3, 4, 5} va S2(3)S_2 (3) = {3, 4, 5}. Ularning kesishmasi {3, 4, 5}ga teng.
      • S1(4)S_1 (4) = {4} va S2(4)S_2 (4) = {4}. Ularning kesishmasi {4}ga teng.
      • S1(5)S_1 (5) = {5} va S2(5)S_2 (5) = {5}. Ularning kesishmasi {5}ga teng.