Ce problème est interactif.

On vous donne un quintuplet $(T,I,S_V,S_E,\iota)$, où :

• $T$ est un arbre enraciné à $n$ sommets, $T=(V,E)$, où $V$ est l'ensemble des sommets et $E$ l'ensemble des arêtes de $T$. Les sommets sont numérotés $1,2,\ldots,n$, et la racine porte le numéro $1$.
• $I$ est un ensemble dont les éléments sont appelés informations. Il contient deux éléments spéciaux distincts : l'élément neutre $\epsilon$ et l'information invalide $\bot$.

Chaque information ordinaire possède deux attributs : un ensemble de sommets et un ensemble d'arêtes. En particulier, l'élément neutre ne possède que l'attribut ensemble d'arêtes, tandis que l'information invalide ne possède aucun de ces deux attributs.

• Pour une information $o\in I\setminus\{\epsilon,\bot\}$, l'ensemble de sommets de $o$ est un sous-ensemble de $V$ à deux éléments, noté $S_V(o)$, avec $S_V(o)\subseteq V$ et $|S_V(o)|=2$. La différence de deux ensembles $A,B$ est définie par $A\setminus B=\{x\in A\mid x\notin B\}$.
• Pour une information $o\in I\setminus\{\bot\}$, l'ensemble d'arêtes de $o$ est un sous-ensemble de $E$, noté $S_E(o)$, avec $S_E(o)\subseteq E$. L'ensemble d'arêtes de l'élément neutre est vide : $S_E(\epsilon)=\varnothing$.
• Pour toute arête $e\in E$ de l'arbre, notée $e=(u,v)$, il existe une information associée $\iota(e)\in I$ dont l'ensemble de sommets est constitué des extrémités de l'arête et dont l'ensemble d'arêtes ne contient qu'elle-même : $S_V(\iota(e))=\{u,v\}$ et $S_E(\iota(e))=\{e\}$.

Il existe deux opérations de fusion des informations, notées $R$ et $C$. Pour tous $a,b\in I$, notons $r=R(a,b)$ et $c=C(a,b)$, avec $r,c\in I$. Alors :

• Fusionner l'élément neutre avec n'importe quelle information donne cette dernière. Autrement dit, si $a=\epsilon$, alors $r=c=b$ ; si $b=\epsilon$, alors $r=c=a$.
• Fusionner l'information invalide avec n'importe quelle information donne l'information invalide. Autrement dit, si $a=\bot$ ou $b=\bot$, alors $r=c=\bot$.
• Dans les autres cas, si l'intersection des ensembles d'arêtes des deux informations n'est pas vide, ou si l'intersection de leurs ensembles de sommets n'a pas exactement un élément, la fusion donne l'information invalide. Autrement dit, si $S_E(a)\cap S_E(b)\ne\varnothing$ ou $|S_V(a)\cap S_V(b)|\ne1$, alors $r=c=\bot$.
• Sinon :

$$ 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). $$

Ici, $\oplus$ désigne la différence symétrique des ensembles : $A\oplus B=(A\cup B)\setminus(A\cap B)$.

La distance dans l'arbre entre deux sommets de $T$ est le nombre d'arêtes de l'unique chemin simple qui les relie.

On vous donne un paramètre de notation $M$ et $q$ requêtes. Chaque requête fournit un sommet $u$ de l'arbre et un entier non négatif $d$. Notons $X$ l'ensemble des sommets de $T$ dont la distance à $u$ dans l'arbre ne dépasse pas $d$, et $Y=\{(a,b)\in E\mid a,b\in X\}$ l'ensemble des arêtes internes à $X$. On peut démontrer qu'en partant de $\epsilon$ et de toutes les informations $\iota(e)$, pour $e\in E$, il est toujours possible d'obtenir, par un nombre fini d'appels à $R,C$, une information $o\ne\bot$ telle que $S_E(o)=Y$.

Pour chaque requête, vous devez construire une telle information $o$ en effectuant au plus $M$ appels au total à $R$ et $C$. En particulier, si $d=0$, il suffit de renvoyer directement l'élément neutre $\epsilon$.

Détails d'implémentation

Assurez-vous de placer #include "count.h" au début de votre programme.

Le fichier d'en-tête count.h fournit les éléments suivants :

1. Le type de données info, qui représente les informations.
2. La constante emptyinfo de type info, correspondant à $\epsilon$, que vous pouvez utiliser directement.
3. Les deux fonctions de fusion suivantes, définies et implémentées, que vous pouvez appeler directement :

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

Ces fonctions renvoient respectivement les informations correspondant à $R(a,b)$ et $C(a,b)$.

Vous devez garantir que le résultat d'un appel à $R(a,b)$ ou $C(a,b)$ n'est pas $\bot$ ; sinon, le programme peut avoir un comportement anormal.

1. La fonction suivante, définie et implémentée, qui détermine si une information est l'élément neutre et que vous pouvez appeler directement :

bool isempty(info a);

Cette fonction renvoie vrai si et seulement si $a$ est l'élément neutre.

Vous pouvez consulter la bibliothèque d'interaction de référence pour connaître davantage de détails d'implémentation.

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

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

• $T$ est le numéro du test, $n$ le nombre de sommets de l'arbre, $q$ le nombre de requêtes, et $M$ le paramètre de notation de ce test.
• Les vecteurs fa et e ont tous deux une longueur de $n-1$. Pour $0\le i<n-1$, $fa[i]$ et $i+2$ sont les deux extrémités de la $i$-ème arête $e_i$, et $e[i]$ est l'élément de type info correspondant à $\iota(e_i)$ mentionné dans l'énoncé. Il est garanti que $fa[i]<i+2$.

info ask(int u, int d);

• Cette fonction reçoit une requête ; le sens des paramètres est donné dans l'énoncé. Vous devez renvoyer, à la fin de la fonction, une information satisfaisant les conditions du problème.

Lors de l'évaluation finale, pour chaque test, la bibliothèque d'interaction appelle exactement une fois init, puis appelle $q$ fois ask. Elle utilise une implémentation particulière dans laquelle une variable de type info occupe toujours 12 octets, ce qui diffère de la bibliothèque de référence fournie. Pour respecter la limite de mémoire pendant l'exécution, vous devez veiller à ne pas avoir trop de variables de type info simultanément en mémoire.

Il est garanti que, lorsque les limites du nombre d'appels sont respectées et qu'aucun appel à isempty n'est effectué, la bibliothèque d'évaluation finale prend au plus 0,6 seconde et utilise elle-même au plus 16 Mio de mémoire. Il est également garanti que, pour la seule exécution de $10^8$ appels à isempty, la bibliothèque d'évaluation finale prend au plus 0,25 seconde.

Les fichiers fournis comprennent un programme d'exemple nommé count.cpp, à partir duquel vous pouvez poursuivre l'implémentation. Ils comprennent également un fichier de sauvegarde count_backup.h, garanti strictement identique à count.h.

Test du programme

Le répertoire du problème fournit deux implémentations de référence de la bibliothèque d'interaction, grader.o et checker.o. Il s'agit de fichiers objets pouvant être liés, obtenus en compilant deux bibliothèques différentes. L'implémentation utilisée lors de l'évaluation finale diffère de celles-ci : votre solution ne doit donc pas dépendre de l'implémentation particulière de la bibliothèque d'interaction, ni de celle du type info dans count.h.

Vous devez modifier le fichier count.h fourni pour permettre l'édition de liens. Plus précisément, pour lier le code source count.cpp à grader.o, commentez la ligne 5 de count.h et conservez la ligne 4. De même, pour lier checker.o, commentez la ligne 4 et conservez la ligne 5. Vous pouvez modifier vous-même l'implémentation de count.h afin de compiler les différents programmes.

Après ces modifications, vous pouvez utiliser les commandes suivantes dans le répertoire du problème pour compiler un exécutable :

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

La première commande compile le fichier count.cpp courant, puis le lie à grader.o pour produire l'exécutable count. La seconde compile le fichier count.cpp courant, puis le lie à checker.o pour produire l'exécutable count.

L'exécutable count obtenu de cette manière fonctionne comme suit :

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

  • La première ligne contient quatre entiers $id,n,q,M$, respectivement le numéro du test, le nombre de sommets, le nombre de requêtes et le paramètre de notation.
  • La deuxième ligne contient $n-1$ entiers $p_2,p_3,\ldots,p_n$, les numéros des parents des sommets $2$ à $n$. Lors du débogage local, vous devez garantir que $\forall i\in[2,n],\ p_i<i$.
  • Les $q$ lignes suivantes contiennent chacune deux entiers $u,d$, décrivant une requête.

• Après la lecture, la bibliothèque d'interaction effectue les tests. Si votre programme ne respecte pas ses restrictions, elle renvoie le message d'erreur correspondant dans la sortie. Sinon, l'exécutable lié produit la sortie suivante :

  • Une seule ligne contenant trois entiers $C_1,C_2,C_3$, où :

    • $C_1$ est le nombre total d'appels aux fonctions de la bibliothèque effectués dans init.
    • $C_2$ est le nombre total d'appels aux fonctions de la bibliothèque pendant toute l'exécution.
    • $C_3$ est le maximum du nombre d'appels aux fonctions de la bibliothèque effectués dans un appel à ask, parmi les $q$ appels.
    • Pour ces trois statistiques, seuls les appels à MR et MC sont comptés ; les appels à isempty ne le sont pas.

• Les vérifications possibles dépendent du fichier lié :

  • grader.o : pendant l'exécution, il ne vérifie pas que l'information renvoyée par ask est correcte, mais peut vous aider à déterminer si les opérations d'interaction respectent les exigences. Son temps d'exécution est le plus proche de celui de la bibliothèque d'évaluation ; vous pouvez donc l'utiliser pour tester la vitesse d'exécution, mais il ne garantit pas la correction du programme.
  • checker.o : pendant l'exécution, il vérifie que l'information renvoyée par ask est correcte et peut également vous aider à déterminer si les opérations d'interaction respectent les exigences. Il vérifie aussi que l'information renvoyée par ask est correcte. Ce programme permet de vérifier la correction des réponses.

Pendant le débogage, assurez-vous que les données fournies à l'exécutable count respectent le format d'entrée ci-dessus ; sinon, la correction de la sortie n'est pas garantie.

Exemples

Exemple 1

Voir count/count1.in et count/count1.ans dans le répertoire du candidat.

Exemple 2

Voir count/count2.in et count/count2.ans dans le répertoire du candidat.

Cet exemple satisfait la propriété spéciale A des contraintes.

Exemple 3

Voir count/count3.in et count/count3.ans dans le répertoire du candidat.

Cet exemple satisfait la propriété spéciale B des contraintes.

Exemple 4

Voir count/count4.in et count/count4.ans dans le répertoire du candidat.

Sous-tâches

Seul count.cpp est récupéré pour l'évaluation finale. Modifier les autres fichiers du répertoire du candidat n'a aucun effet sur le résultat. Attention :

• Une variable de type info non initialisée n'est pas nécessairement égale à emptyinfo.
• N'essayez pas d'accéder aux variables membres du type info, ni de les modifier : cela serait considéré comme une attaque contre la bibliothèque d'interaction.
• N'appelez pas MR ni MC avant l'appel à init, car cela peut provoquer un comportement indéfini.
• Vous ne pouvez accéder qu'aux variables que vous avez vous-même définies et aux variables de type info renvoyées par la bibliothèque. Toute tentative d'accès à d'autres espaces peut entraîner une erreur de compilation ou d'exécution.

Ce problème est d'abord soumis aux mêmes restrictions que les problèmes classiques. Par exemple, une erreur de compilation donne 0 point pour l'ensemble du problème ; une erreur d'exécution, un dépassement de la limite de temps ou de mémoire, etc., donne 0 point pour le test concerné.

En outre, si, lors d'un test, le programme effectue un appel de fonction illégal ou donne une réponse incorrecte à une requête, il obtient 0 point pour ce test. Sinon, notons $C_1$ le nombre d'appels aux fonctions de la bibliothèque effectués dans init, et $C_3$ le maximum de ce nombre parmi les $q$ appels à ask. Si $C_1\le3\cdot10^7$ et que $C_3$ ne dépasse pas le paramètre de notation $M$ du test, vous obtenez les points de ce test ; sinon, vous ne les obtenez pas. Remarque : seuls les appels à MR et MC sont comptés dans $C_1,C_3$ ; les appels à isempty ne le sont pas.

Contraintes

Pour tous les tests, $1\le n\le2\cdot10^5$ et $1\le q\le10^6$. Pour chaque requête, $1\le u\le n$ et $1\le d\le n-1$.

Propriété spéciale A : pour tout $i\in[1,n-1]$, le parent du sommet $i+1$ est $i$.

Propriété spéciale B : toutes les requêtes satisfont $u=1$.

Propriété spéciale C : toutes les requêtes satisfont $d\le100$.

Propriété spéciale D : toutes les requêtes satisfont $d\ge1000$.