Latar Belakang

Ini adalah soal interaktif.

Ilmuwan hebat 欣 berencana membangun kecerdasan buatan kuat 隆 untuk menguasai dunia. Setelah memasukkan beberapa soal kompetisi algoritma dari Vietnam sebagai data pelatihan, ia mendapati bahwa 隆 secara otomatis menghasilkan sebuah soal baru beserta solusinya. 隆 juga mereduksi 30% data masukan dalam himpunan pengujian ke soal ini.

欣 segera menyalin soal tersebut sebagai berikut:

Diberikan sebuah pohon berakar, Anda perlu mendukung dua operasi:

• Menanyakan jumlah elemen pada suatu lintasan pohon.
• Mengubah induk sebuah simpul menjadi simpul lain.

“Soal ini tidak terlalu sulit. Mengapa bisa menyelesaikan 30% soal dalam himpunan pengujian?” pikir 欣.

Sebelum menutup halaman hasil pelatihan, 欣 tiba-tiba menyadari bahwa dalam soal yang diberikan 隆, biaya penggabungan informasi bukan $O(1)$.

欣 merenung dan menyadari bahwa ia tidak bisa menyelesaikan soal ini.

Untuk mengetahui seberapa sulit soal ini, 欣 menyajikannya kepada Anda.

Deskripsi

Anda perlu memelihara sebuah pohon berakar di $1$ dengan $n$ simpul. Awalnya, untuk setiap $2 \le i \le n$, simpul $i$ memiliki induk $p_i$, dan dijamin $p_i \lt i$.

Awalnya Anda memiliki $n$ himpunan $\{1\},\{2\},\cdots,\{n\} $. Untuk sembarang dua himpunan $A$ dan $B$, jika $A \cap B=\varnothing$, Anda dapat memperoleh himpunan $A \cup B$ dengan satu operasi berbiaya $|A|+|B|$.

Selanjutnya terdapat $q$ operasi. Setiap operasi memiliki salah satu dari dua jenis berikut:

• 0 a b: Misalkan $S$ adalah himpunan simpul pada lintasan dari $a$ ke $b$ di pohon. Anda perlu menyatakan $S$ sebagai $\cup_{i=1}^{k}A_i$, dengan setiap $A_i$ merupakan himpunan yang sudah Anda peroleh, dan $\forall i \neq j,A_i \cap A_j=\varnothing$. Biaya menjawab satu kueri dengan $(A_1,A_2,\cdots,A_k) $ adalah $k$.
• 1 a b: Mengubah induk simpul $a$ menjadi $b$. Dijamin $a \gt 1$ dan setelah perubahan, $n$ simpul ini tetap membentuk pohon, tetapi tidak dijamin $a \gt b$. Dalam operasi ini, Anda boleh menghasilkan beberapa himpunan baru untuk menjawab kueri berikutnya.

Misalkan biaya total selama eksekusi program adalah $C_1$, dan biaya maksimum dalam satu operasi adalah $C_2$. Setiap subsoal memberikan nilai dengan cara tertentu berdasarkan besarnya $C_1,C_2$.

Detail Implementasi

Pastikan program Anda diawali dengan #include "long.h".

Berkas header mendefinisikan tipe data infoset untuk menyimpan himpunan yang Anda peroleh.

Tipe ini memiliki fungsi anggota size() yang menyatakan ukuran himpunan. Header juga menyediakan konstanta emptyset yang menyatakan himpunan kosong.

Anda juga dapat memanggil fungsi berikut:

infoset merge(const infoset&A,const infoset&B);

• Menghasilkan himpunan baru $A \cup B$ dengan biaya tertentu.
• Anda boleh menghasilkan himpunan yang sama berulang kali, dan biayanya harus dihitung setiap kali.

void report(infoset A);

• Fungsi ini hanya boleh dipanggil selama operasi kueri. Pemanggilan ini menambahkan himpunan $A$ ke gabungan akhir dengan biaya $1$.

Anda tidak perlu dan tidak boleh mengimplementasikan fungsi utama. Anda perlu mengimplementasikan fungsi berikut:

void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);

• Anda boleh melakukan praproses informasi sebelum $q$ operasi dimulai.
• Biaya dalam fungsi ini tidak dihitung ke dalam biaya maksimum satu operasi, tetapi dihitung ke dalam biaya total selama eksekusi program.
• id menyatakan nomor subsoal, n menyatakan jumlah simpul, dan q menyatakan jumlah operasi.
• Ukuran dad adalah $n-1$; dad[i] menyatakan induk simpul $i+2$ pada keadaan awal.
• Ukuran ve adalah $n$; ve[i] menyatakan himpunan awal $\{i+1\}$.

void modify(int x,int y);

• Melakukan satu operasi perubahan, menetapkan simpul $y$ sebagai induk simpul $x$.

void ask(int x,int y);

• Melakukan satu operasi kueri untuk informasi lintasan pohon dari $x$ ke $y$.
• Anda perlu memanggil report beberapa kali untuk menjawab kueri. Setelah kueri berakhir, pustaka interaksi memeriksa apakah semua himpunan $A$ yang Anda laporkan memenuhi persyaratan.

Saat penilaian, pustaka interaksi memanggil init sekali, lalu memanggil modify dan ask sebanyak $q$ kali secara keseluruhan.

Bentuk pohon dan operasi yang dilakukan dijamin sudah sepenuhnya ditentukan sebelum interaksi dimulai, dan tidak dibangun secara dinamis berdasarkan interaksi dengan program Anda. Karena itu, operasi interaktif dalam soal ini bersifat deterministik; Anda tidak perlu memikirkan implementasi terperincinya dalam pustaka interaksi.

Saat penilaian, pustaka interaksi menggunakan implementasi khusus sehingga setiap variabel bertipe infoset selalu memakai $8$ bita memori. Pastikan tidak terlalu banyak variabel bertipe infoset yang ada secara bersamaan selama eksekusi program.

Dijamin, dengan batas jumlah pemanggilan yang ditentukan, waktu eksekusi pustaka interaksi tidak melebihi 2 detik; memori yang digunakan pustaka itu sendiri tidak melebihi 16 MB.

Cara Menguji Program

Berkas grader.cpp yang disertakan adalah implementasi referensi pustaka interaksi yang kami sediakan. Implementasi yang digunakan dalam pengujian akhir berbeda dari implementasi referensi ini, sehingga solusi peserta tidak boleh bergantung pada implementasi pustaka interaksi.

Gunakan perintah berikut untuk mengompilasi program menjadi berkas yang dapat dieksekusi:

g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

Untuk program hasil kompilasi:

• Program membaca data dari masukan standar dengan format berikut:

  • Baris pertama berisi satu bilangan bulat $id$, yaitu nomor subsoal.
  • Baris kedua berisi dua bilangan bulat $n,q$, yaitu jumlah simpul dan jumlah operasi.
  • Baris ketiga berisi $n-1$ bilangan bulat, yaitu nomor induk simpul ke-$2$ hingga ke-$n$ secara berurutan.
  • $q$ baris berikutnya masing-masing berisi tiga bilangan bulat $op,x,y$ yang mendeskripsikan satu operasi. $op=0$ menyatakan kueri, dan $op=1$ menyatakan perubahan.
• Setelah selesai membaca, pustaka interaksi memanggil init tepat sekali dan modify atau ask sebanyak $q$ kali, menggunakan data masukan untuk menguji fungsi Anda. Setelah berjalan normal, program mengeluarkan beberapa baris, masing-masing berisi beberapa bilangan yang menyatakan jawaban Anda untuk setiap kueri. Baris terakhir memuat dua bilangan bulat $W_1,W_2$, yaitu biaya total eksekusi program dan biaya maksimum satu operasi.

Berkas yang disertakan memuat empat kelompok contoh; kelompok keempat memenuhi sifat khusus subsoal dua. Saat menguji contoh, abaikan perbandingan baris terakhir berkas keluaran, karena baris terakhir yang dikeluarkan pustaka interaksi menyatakan biaya eksekusi program, bukan hasil kueri.

Penilaian

Soal ini terlebih dahulu tunduk pada batasan yang sama seperti soal biasa. Misalnya, kesalahan kompilasi menyebabkan nilai $0$ untuk seluruh soal, sedangkan kesalahan saat eksekusi, melebihi batas waktu, atau melebihi batas memori menyebabkan nilai $0$ untuk kasus uji terkait. Anda hanya boleh mengakses variabel yang Anda definisikan sendiri dan yang disediakan pustaka interaksi beserta ruang memori terkaitnya. Percobaan mengakses ruang lain dapat menyebabkan kesalahan kompilasi atau kesalahan saat eksekusi.

Selain ketentuan di atas, jika pada sebuah kasus uji program memanggil fungsi secara tidak sah, tidak berhenti secara normal, atau memberikan jawaban kueri yang salah, nilai kasus uji tersebut adalah $0$. Jika tidak, terdapat dua cara penilaian berdasarkan biaya program Anda:

• Cara I: Jika $W_1 \gt 6 \cdot 10^8$, nilai kasus uji adalah $0$; jika tidak, nilainya adalah $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times \text{nilai subsoal yang memuat kasus uji tersebut}$.
• Cara II: Jika $W_2 \gt 2 \cdot 10^4$, nilai kasus uji adalah $0$; jika tidak, nilainya adalah $\frac{5000}{max(W_2,5000)} \times \text{nilai subsoal yang memuat kasus uji tersebut}$.

Subsoal yang berbeda menggunakan cara penilaian yang berbeda. Nilai sebuah subsoal adalah nilai minimum dari seluruh kasus ujinya.

Batasan dan Ketentuan

Untuk seluruh kasus uji, dijamin $1 \le n,q \le 10^5$.

Sifat khusus: Pada setiap saat, setiap simpul selain simpul $1$ dijamin memiliki paling banyak satu anak.

Epilog

欣 mendapati bahwa setelah lima jam Anda masih belum berhasil menyelesaikan soal ini dan merasa sangat puas dengan kemampuan 隆. Namun, saat bangun keesokan paginya, 欣 tiba-tiba menyadari bahwa pembuktian kompleksitas solusi 隆 salah.