Ceci est un problème interactif.

La grande scientifique 欣 prépare la construction de 隆, une intelligence artificielle forte destinée à dominer le monde. Après lui avoir fourni des problèmes vietnamiens de compétition d'algorithmique comme ensemble d'entraînement, elle découvre que 隆 a automatiquement créé un nouveau problème et en a fourni une solution. 隆 a également réduit 30 % des données d'entrée de l'ensemble de test à ce problème. 欣 s'empresse de recopier le problème : Étant donné un arbre enraciné, vous devez prendre en charge deux opérations :

• Calculer la somme des éléments d'un chemin dans l'arbre.
• Remplacer le parent d'un sommet par un autre sommet.

« Ce problème n'est pas si puissant ; pourquoi permet-il de résoudre 30 % des problèmes de l'ensemble de test ? », se demande 欣. Avant de fermer la page des résultats d'entraînement, 欣 remarque soudain que, dans le problème proposé par 隆, le coût de fusion des informations n'est pas $O(1)$. Après réflexion, 欣 se rend compte qu'elle ne sait pas résoudre ce problème. Pour découvrir sa difficulté, 欣 vous le soumet.

Énoncé

Vous devez maintenir un arbre de $n$ sommets, enraciné au sommet $1$. Initialement, pour tout $2 \le i \le n$, le sommet $i$ a pour parent $p_i$, avec $p_i \lt i$.

Au départ, vous disposez des $n$ ensembles $\{1\},\{2\},\cdots,\{n\} $. Pour deux ensembles quelconques $A$ et $B$, si $A \cap B=\varnothing$, vous pouvez obtenir l'ensemble $A \cup B$ en une opération de coût $|A|+|B|$.

Ensuite ont lieu $q$ opérations, chacune de l'un des deux types suivants :

• 0 a b : soit $S$ l'ensemble des sommets du chemin entre $a$ et $b$ dans l'arbre. Vous devez représenter $S$ sous la forme $\cup_{i=1}^{k}A_i$, où chaque $A_i$ est un ensemble que vous avez déjà obtenu et où $\forall i \neq j,A_i \cap A_j=\varnothing$. Répondre à une requête par $(A_1,A_2,\cdots,A_k) $ coûte $k$.
• 1 a b : remplacer le parent du sommet $a$ par $b$. Il est garanti que $a \gt 1$ et que les $n$ sommets forment encore un arbre après la modification, mais il n'est pas garanti que $a \gt b$. Vous pouvez créer de nouveaux ensembles pendant cette opération pour traiter les requêtes suivantes.

Notons $C_1$ le coût total consommé pendant toute l'exécution de votre programme et $C_2$ le coût maximal d'une seule opération. Chaque sous-tâche attribue des points selon une certaine règle en fonction des valeurs de $C_1,C_2$.

Détails d'implémentation

Veillez à placer #include "long.h" au début de votre programme.

Ce fichier d'en-tête définit le type infoset, qui sert à stocker les ensembles que vous obtenez.

Ce type possède une fonction membre size() qui indique la taille de l'ensemble. Le fichier d'en-tête fournit aussi la constante emptyset, qui représente l'ensemble vide.

Vous pouvez également appeler les fonctions suivantes :

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

• Crée un nouvel ensemble $A \cup B$ moyennant un certain coût.
• Vous pouvez créer plusieurs fois le même ensemble ; le coût est comptabilisé à chaque fois.

void report(infoset A);

• Vous ne pouvez appeler cette fonction que pendant une requête. Elle ajoute un ensemble $A$ à l'union finale, pour un coût de $1$.

Vous n'avez pas besoin d'implémenter la fonction principale, et vous ne devez pas le faire. Vous devez implémenter les fonctions suivantes :

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

• Vous pouvez précalculer certaines informations avant le début des $q$ opérations.
• Le coût consommé dans cette fonction ne compte pas dans le coût maximal d'une seule opération, mais compte dans le coût total consommé pendant toute l'exécution du programme.
• id est le numéro de la sous-tâche, n le nombre total de sommets et q le nombre total d'opérations.
• dad est de taille $n-1$ ; dad[i] est le parent initial du sommet $i+2$.
• ve est de taille $n$ ; ve[i] est l'ensemble initial $\{i+1\}$.

void modify(int x,int y);

• Effectue une modification, en remplaçant le parent du sommet $x$ par le sommet $y$.

void ask(int x,int y);

• Effectue une requête sur les informations du chemin de $x$ à $y$ dans l'arbre.
• Vous devez appeler report un certain nombre de fois pour répondre. À la fin de la requête, la bibliothèque d'interaction vérifie si tous les ensembles $A$ que vous avez signalés satisfont les conditions.

Lors de l'évaluation, la bibliothèque d'interaction appelle d'abord init une fois, puis appelle modify et ask un total de $q$ fois.

La forme de l'arbre et les opérations à effectuer sont entièrement déterminées avant le début de l'interaction ; elles ne sont pas construites dynamiquement en fonction des échanges avec votre programme. Les opérations interactives de ce problème sont donc déterministes, et vous n'avez pas à vous préoccuper de leur implémentation précise dans la bibliothèque d'interaction.

Lors de l'évaluation, la bibliothèque utilise une implémentation spéciale : chaque variable de type infoset occupe toujours $8$ octets de mémoire. Veillez à ne pas conserver simultanément un trop grand nombre de variables de ce type pendant l'exécution de votre programme.

Il est garanti que, sous les limites du nombre d'appels, la bibliothèque d'interaction nécessite au plus 2 s de temps d'exécution et utilise elle-même au plus 16 Mo de mémoire.

Test de votre programme

Le fichier grader.cpp fourni est une implémentation de référence de la bibliothèque d'interaction. L'implémentation utilisée lors de l'évaluation finale est différente ; votre solution ne doit donc pas dépendre de l'implémentation de la bibliothèque.

Compilez votre exécutable avec la commande suivante : g++ grader.cpp long.cpp -o long -static -O2 -std=c++14

Pour l'exécutable ainsi obtenu :

• L'exécutable lit sur l'entrée standard des données au format suivant :

  • La première ligne contient un entier $id$, le numéro de la sous-tâche.
  • La deuxième ligne contient deux entiers $n,q$, le nombre total de sommets et le nombre total d'opérations.
  • La troisième ligne contient $n-1$ entiers, les numéros des parents des sommets $2$ à $n$, dans cet ordre.
  • Les $q$ lignes suivantes contiennent chacune trois entiers $op,x,y$ décrivant une opération. $op=0$ indique une requête et $op=1$ une modification.
• Après la lecture, la bibliothèque appelle exactement une fois init et $q$ fois modify ou ask, afin de tester vos fonctions avec les données d'entrée. Si le programme s'exécute normalement, il affiche plusieurs lignes contenant chacune plusieurs nombres représentant vos réponses aux requêtes. La dernière ligne contient deux entiers $W_1,W_2$, qui indiquent respectivement le coût total consommé par votre programme et le coût maximal d'une seule opération.

Les fichiers fournis comprennent quatre jeux de fichiers d'exemple ; le quatrième satisfait la propriété particulière de la sous-tâche 2. Lors du test des exemples, ignorez la comparaison de la dernière ligne du fichier de sortie : cette ligne contient le coût d'exécution du programme et non le résultat d'une requête.

Sous-tâches

Ce problème est d'abord soumis aux mêmes contraintes qu'un problème classique. Par exemple, une erreur de compilation donne $0$ point pour tout le problème ; une erreur d'exécution, un dépassement du temps ou de la mémoire donne $0$ point pour le test concerné. Vous ne pouvez accéder qu'aux variables que vous définissez et à celles fournies par la bibliothèque d'interaction, ainsi qu'à leurs zones de mémoire respectives. Tenter d'accéder à d'autres zones peut entraîner une erreur de compilation ou d'exécution.

En plus des conditions ci-dessus, si votre programme effectue un appel de fonction illégal, ne se termine pas normalement ou donne une réponse incorrecte à une requête, le test reçoit $0$ point. Sinon, deux méthodes de notation sont possibles, selon le coût consommé :

• Méthode I : si $W_1 \gt 6 \cdot 10^8$, le test reçoit $0$ point ; sinon, son score est $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times \text{score de la sous-tâche contenant ce test}$.
• Méthode II : si $W_2 \gt 2 \cdot 10^4$, le test reçoit $0$ point ; sinon, son score est $\frac{5000}{max(W_2,5000)} \times \text{score de la sous-tâche contenant ce test}$.

Les différentes sous-tâches utilisent des méthodes de notation différentes. Le score d'une sous-tâche est le minimum des scores de tous ses tests.

Contraintes

Pour tous les tests, $1 \le n,q \le 10^5$.

Propriété particulière : à tout instant, chaque sommet autre que le sommet $1$ possède au plus un enfant.

Épilogue

Voyant que vous n'avez toujours pas résolu ce problème après cinq heures, 欣 est très satisfaite des capacités de 隆. Mais, le lendemain matin, elle découvre soudain que la preuve de complexité de la méthode de 隆 est fausse.