Ini adalah soal interaktif.

Diberikan sebuah kuintupel $(T,I,S_V,S_E,\iota)$, dengan:

• $T$ adalah pohon berakar dengan $n$ simpul, $T=(V,E)$, dengan $V$ merupakan himpunan simpul $T$ dan $E$ merupakan himpunan sisi $T$. Simpul-simpul pohon diberi nomor $1,2,\ldots,n$, dengan akar bernomor $1$.
• $I$ adalah sebuah himpunan yang elemen-elemennya disebut informasi. Terdapat dua elemen khusus yang berbeda: elemen identitas $\epsilon$ dan informasi tidak sah $\bot$.

Informasi biasa memiliki dua atribut, yaitu himpunan simpul dan himpunan sisi. Secara khusus, elemen identitas hanya memiliki atribut himpunan sisi, sedangkan informasi tidak sah tidak memiliki kedua atribut tersebut.

• Untuk informasi $o\in I\setminus\{\epsilon,\bot\}$, himpunan simpul $o$ adalah sebuah subhimpunan dari $V$ yang beranggotakan dua elemen, dinotasikan $S_V(o)$, dengan $S_V(o)\subseteq V$ dan $|S_V(o)|=2$. Selisih dua himpunan $A,B$ didefinisikan sebagai $A\setminus B=\{x\in A\mid x\notin B\}$.
• Untuk informasi $o\in I\setminus\{\bot\}$, himpunan sisi $o$ adalah sebuah subhimpunan dari $E$, dinotasikan $S_E(o)$, dengan $S_E(o)\subseteq E$. Himpunan sisi elemen identitas ditetapkan kosong, yaitu $S_E(\epsilon)=\varnothing$.
• Untuk setiap sisi $e\in E$ pada pohon, misalkan $e=(u,v)$. Terdapat informasi $\iota(e)\in I$ untuk $e$, dengan kedua ujungnya sebagai himpunan simpul dan sisi itu sendiri sebagai himpunan sisi, yaitu $S_V(\iota(e))=\{u,v\}$, $S_E(\iota(e))=\{e\}$.

Terdapat dua cara menggabungkan informasi, dinotasikan $R$ dan $C$. Untuk setiap $a,b\in I$, misalkan $r=R(a,b)$, $c=C(a,b)$, dengan $r,c\in I$. Berlaku:

• Menggabungkan elemen identitas dengan informasi apa pun menghasilkan informasi yang lain tersebut. Yaitu, jika $a=\epsilon$, maka $r=c=b$; jika $b=\epsilon$, maka $r=c=a$.
• Menggabungkan informasi tidak sah dengan informasi apa pun menghasilkan informasi tidak sah. Yaitu, jika $a=\bot$ atau $b=\bot$, maka $r=c=\bot$.
• Dalam kasus-kasus lainnya, jika irisan himpunan sisi kedua informasi tidak kosong, atau ukuran irisan himpunan simpul keduanya bukan $1$, hasil penggabungannya adalah informasi tidak sah. Yaitu, jika $S_E(a)\cap S_E(b)\ne\varnothing$ atau $|S_V(a)\cap S_V(b)|\ne1$, maka $r=c=\bot$.

• Jika tidak, berlaku

  $$S_E(r)=S_E(c)=S_E(a)\cup S_E(b),$$ $$S_V(r)=S_V(a),$$ $$S_V(c)=S_V(a)\oplus S_V(b).$$

  Di sini, $\oplus$ menyatakan operasi beda setangkup himpunan, yaitu $A\oplus B=(A\cup B)\setminus(A\cap B)$.

Jarak pada pohon antara dua simpul di $T$ didefinisikan sebagai jumlah sisi yang dilalui oleh satu-satunya lintasan sederhana dengan kedua simpul tersebut sebagai ujung.

Diberikan parameter penilaian $M$ dan $q$ pertanyaan. Setiap pertanyaan memberikan sebuah simpul $u$ pada pohon dan sebuah bilangan bulat nonnegatif $d$. Misalkan $X$ adalah himpunan semua simpul di $T$ yang jaraknya dari $u$ pada pohon tidak melebihi $d$, dan $Y=\{(a,b)\in E\mid a,b\in X\}$ adalah himpunan sisi di dalam $X$. Dapat dibuktikan bahwa, dengan berawal dari $\epsilon$ dan semua $\iota(e)$ ($e\in E$), informasi $o\ne\bot$ yang memenuhi $S_E(o)=Y$ selalu dapat diperoleh melalui sejumlah berhingga pemanggilan $R,C$.

Untuk setiap pertanyaan, kamu harus membangun informasi $o$ yang memenuhi persyaratan tersebut dengan jumlah total pemanggilan $R$ dan $C$ tidak melebihi $M$. Khususnya, jika $d=0$, cukup kembalikan elemen identitas $\epsilon$ secara langsung.

Detail Implementasi

Pastikan programmu diawali dengan #include "count.h".

Berkas header count.h mengimplementasikan hal-hal berikut:

1. Mendefinisikan tipe data info yang bersesuaian dengan informasi;
2. Mendefinisikan konstanta bertipe info bernama emptyinfo, yang bersesuaian dengan $\epsilon$ dan dapat langsung digunakan dalam program.
3. Mendefinisikan dan mengimplementasikan dua fungsi penggabungan informasi berikut, yang dapat langsung dipanggil dalam program:

info MR(info a,info b);
info MC(info a,info b);

• Kedua fungsi tersebut masing-masing mengembalikan informasi yang bersesuaian dengan $R(a,b)$ dan $C(a,b)$.

Kamu harus memastikan bahwa hasil pemanggilan $R(a,b)$ atau $C(a,b)$ bukan $\bot$; jika tidak, program dapat menunjukkan perilaku abnormal.

1. Mendefinisikan dan mengimplementasikan fungsi untuk menentukan apakah suatu informasi merupakan elemen identitas, yang dapat langsung dipanggil dalam program:

bool isempty(info a);

• Fungsi ini mengembalikan benar jika dan hanya jika $a$ merupakan elemen identitas.

Kamu dapat melihat pustaka interaksi acuan untuk mempelajari detail implementasi lebih lanjut.

Kamu tidak perlu dan tidak boleh mengimplementasikan fungsi utama. Kamu harus mengimplementasikan fungsi-fungsi berikut:

void init(int T, int n, int q, vector<int> fa, vector<info> e, int
   M);

• $T$ menyatakan nomor kasus uji, $n$ menyatakan jumlah simpul pohon, $q$ menyatakan jumlah pertanyaan, dan $M$ menyatakan parameter penilaian kasus uji tersebut.
• Panjang fa dan e sama-sama $n-1$. Untuk $0\le i<n-1$, $fa[i]$ dan $i+2$ adalah kedua ujung sisi ke-$i$, $e_i$, sedangkan $e[i]$ adalah elemen bertipe info yang bersesuaian dengan $\iota(e_i)$ pada deskripsi soal. Data menjamin $fa[i]<i+2$.

info ask(int u, int d);

• Diberikan sebuah pertanyaan, dengan arti parameter seperti pada deskripsi soal. Saat fungsi berakhir, kamu harus mengembalikan informasi yang memenuhi ketentuan soal.

Pada pengujian akhir, untuk setiap kasus uji, pustaka interaksi akan memanggil fungsi init tepat satu kali, kemudian memanggil fungsi ask sebanyak $q$ kali. Pustaka interaksi menggunakan implementasi khusus: satu variabel bertipe info selalu menggunakan 12 byte memori, berbeda dengan pustaka interaksi acuan yang dibagikan. Untuk memastikan penggunaan memori program tetap dalam batas soal, pastikan tidak terlalu banyak variabel bertipe info yang ada secara bersamaan selama program berjalan.

Dijamin bahwa, jika batas jumlah pemanggilan dipenuhi dan fungsi isempty tidak dipanggil, waktu yang dibutuhkan pustaka interaksi pada pengujian akhir tidak melebihi 0.6 detik dan penggunaan memori pustaka itu sendiri tidak melebihi 16 MiB. Dijamin pula bahwa, jika hanya dilakukan $10^8$ pemanggilan fungsi isempty, waktu yang dibutuhkan pustaka interaksi pada pengujian akhir tidak melebihi 0.25 detik.

Berkas yang dibagikan mencakup sebuah berkas bernama count.cpp sebagai program contoh, yang dapat dikembangkan peserta untuk mengimplementasikan soal ini. Berkas yang dibagikan juga mencakup cadangan bernama count_backup.h, yang dijamin persis sama dengan count.h.

Cara Menguji Program

Direktori soal ini menyediakan dua implementasi acuan pustaka interaksi, grader.o, checker.o, yaitu berkas yang dapat ditautkan hasil kompilasi dua pustaka interaksi berbeda. Implementasi pustaka interaksi pada pengujian akhir berbeda dari implementasi tersebut. Oleh karena itu, solusi peserta tidak boleh bergantung pada implementasi khusus pustaka interaksi, dan juga tidak boleh bergantung pada implementasi khusus tipe info dalam count.h.

Kamu perlu mengubah count.h yang dibagikan untuk membantu proses penautan. Secara khusus, saat menautkan kode sumber count.cpp dengan grader.o, komentari baris ke-5 dalam count.h dan pertahankan kode pada baris ke-4. Cara menautkan checker.o serupa: komentari baris ke-4 dalam count.h dan pertahankan kode pada baris ke-5. Peserta boleh mengubah implementasi count.h sendiri untuk mengompilasi program yang berbeda.

Setelah melakukan perubahan, peserta dapat menggunakan perintah berikut dalam direktori soal ini untuk menghasilkan program yang dapat dijalankan:

g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o grader.o -o count
g++ count.cpp -c -O2 -std=c++14 -lm && g++ count.o checker.o -o count

Perintah pada baris pertama mengompilasi count.cpp saat ini, kemudian menautkannya dengan grader.o untuk menghasilkan berkas count yang dapat dijalankan. Perintah pada baris kedua mengompilasi count.cpp saat ini, kemudian menautkannya dengan checker.o untuk menghasilkan berkas count yang dapat dijalankan.

Berkas count yang dikompilasi dengan cara di atas dijalankan sebagai berikut:

• Program membaca data dari masukan standar dengan format berikut:
  • Baris pertama memuat empat bilangan bulat $id,n,q,M$, masing-masing menyatakan nomor kasus uji, jumlah simpul pohon, jumlah pertanyaan, dan parameter penilaian;
  • Baris kedua memuat $n-1$ bilangan bulat $p_2,p_3,\ldots,p_n$, masing-masing menyatakan nomor orang tua simpul $2$ hingga $n$. Saat melakukan debug secara lokal, kamu harus memastikan bahwa untuk setiap $i\in[2,n]$, berlaku $p_i<i$;
  • Sebanyak $q$ baris berikutnya masing-masing memuat dua bilangan bulat $u,d$ yang mendeskripsikan sebuah pertanyaan.
• Setelah membaca masukan, pustaka interaksi akan melakukan pengujian. Jika programmu tidak memenuhi batasan pustaka interaksi, pesan kesalahan terkait akan ditampilkan pada keluaran. Jika tidak, keluaran program yang ditautkan adalah sebagai berikut:
  • Satu baris berisi tiga bilangan bulat $C_1,C_2,C_3$, dengan:
    • $C_1$ menyatakan jumlah total pemanggilan fungsi pustaka interaksi oleh program dalam fungsi init;
    • $C_2$ menyatakan jumlah total pemanggilan fungsi pustaka interaksi selama program berjalan;
    • $C_3$ menyatakan jumlah maksimum pemanggilan fungsi pustaka interaksi oleh program dalam satu pemanggilan ask, di antara $q$ pemanggilan fungsi tersebut.
    • Ketiga statistik di atas hanya menghitung pemanggilan fungsi MR, MC, dan tidak menghitung pemanggilan fungsi isempty.
• Pemeriksaan yang dapat dilakukan berbeda ketika menautkan berkas yang berbeda. Secara khusus:
  • grader.o: saat berjalan, program ini tidak memeriksa kebenaran informasi yang dikembalikan fungsi ask, tetapi dapat membantu peserta menentukan apakah operasi interaksi memenuhi persyaratan. Waktu jalannya paling mendekati pustaka interaksi saat penilaian, sehingga peserta dapat menggunakannya untuk menguji kecepatan, tetapi program ini tidak menjamin kebenaran program peserta.
  • checker.o: saat berjalan, program ini memeriksa kebenaran informasi yang dikembalikan fungsi ask dan juga dapat membantu peserta menentukan apakah operasi interaksi memenuhi persyaratan. Program ini juga memeriksa kebenaran informasi yang dikembalikan fungsi ask. Program ini dapat digunakan untuk memeriksa kebenaran jawaban.

Saat melakukan debug, peserta harus memastikan bahwa data yang dimasukkan ke program count memenuhi format masukan di atas; jika tidak, kebenaran keluaran tidak dijamin.

Contoh

Contoh 1

Lihat count/count1.in dan count/count1.ans dalam direktori peserta.

Contoh 2

Lihat count/count2.in dan count/count2.ans dalam direktori peserta.

Contoh ini memenuhi sifat khusus A pada bagian Batasan.

Contoh 3

Lihat count/count3.in dan count/count3.ans dalam direktori peserta.

Contoh ini memenuhi sifat khusus B pada bagian Batasan.

Contoh 4

Lihat count/count4.in dan count/count4.ans dalam direktori peserta.

Penilaian

Pada penilaian akhir, hanya count.cpp yang dikumpulkan. Mengubah berkas lain dalam direktori peserta tidak akan memengaruhi hasil penilaian. Perhatikan:

• Variabel bertipe info yang belum diinisialisasi tidak dijamin bernilai emptyinfo.
• Jangan mencoba mengakses atau mengubah variabel anggota tipe info; jika dilakukan, hal itu akan dianggap sebagai serangan terhadap pustaka interaksi.
• Jangan memanggil fungsi MR dan MC sebelum fungsi init dipanggil; jika dilakukan, dapat terjadi perilaku tak terdefinisi.
• Kamu hanya boleh mengakses variabel yang kamu definisikan sendiri dan variabel bertipe info yang dikembalikan pustaka interaksi. Mencoba mengakses ruang lain dapat menyebabkan kesalahan kompilasi atau kesalahan saat program berjalan.

Pertama-tama, soal ini memiliki batasan yang sama dengan soal biasa. Misalnya, kesalahan kompilasi menyebabkan nilai 0 untuk seluruh soal, sedangkan kesalahan saat berjalan, pelanggaran batas waktu, pelanggaran batas memori, dan sebagainya menyebabkan nilai 0 untuk kasus uji terkait.

Di luar ketentuan di atas, jika program melakukan pemanggilan fungsi yang tidak sah atau memberikan jawaban yang salah pada operasi pertanyaan dalam suatu kasus uji, kasus uji tersebut mendapat 0 poin. Jika tidak, misalkan $C_1$ adalah jumlah pemanggilan fungsi pustaka interaksi oleh program dalam fungsi init, dan $C_3$ adalah jumlah maksimum pemanggilan fungsi pustaka interaksi oleh program dalam satu pemanggilan ask, di antara seluruh $q$ pemanggilan fungsi tersebut. Jika $C_1\le3\cdot10^7$ dan $C_3$ tidak melebihi parameter penilaian $M$ untuk kasus uji tersebut, kamu memperoleh poin kasus uji itu; jika tidak, kamu tidak memperoleh poin kasus uji itu. Perhatikan: perhitungan $C_1,C_3$ hanya mencakup pemanggilan fungsi MR, MC, dan tidak mencakup pemanggilan fungsi isempty.

Batasan

Untuk semua kasus uji, $1\le n\le2\cdot10^5$, $1\le q\le10^6$; dalam setiap pertanyaan, $1\le u\le n$, $1\le d\le n-1$.

Sifat khusus A: dijamin bahwa untuk setiap $i\in[1,n-1]$, orang tua simpul bernomor $i+1$ adalah $i$.

Sifat khusus B: dijamin semua pertanyaan memenuhi $u=1$.

Sifat khusus C: dijamin semua pertanyaan memenuhi $d\le100$.

Sifat khusus D: dijamin semua pertanyaan memenuhi $d\ge1000$.