Este es un problema interactivo.

Se da la quíntupla $(T,I,S_V,S_E,\iota)$, donde:

• $T$ es un árbol con raíz de $n$ vértices, $T=(V,E)$, donde $V$ es su conjunto de vértices y $E$ su conjunto de aristas. Los vértices están numerados $1,2,\ldots,n$, y la raíz tiene el número $1$.
• $I$ es un conjunto cuyos elementos se denominan información. Tiene dos elementos especiales distintos: el elemento neutro $\epsilon$ y la información no válida $\bot$.

La información ordinaria tiene dos atributos: un conjunto de vértices y un conjunto de aristas. En particular, el elemento neutro solo tiene el atributo de conjunto de aristas, mientras que la información no válida no tiene ninguno de estos dos atributos.

• Para una información $o\in I\setminus\{\epsilon,\bot\}$, su conjunto de vértices es un subconjunto de dos elementos de $V$, denotado por $S_V(o)$, que satisface $S_V(o)\subseteq V$ y $|S_V(o)|=2$. La diferencia de dos conjuntos $A,B$ se define como $A\setminus B=\{x\in A\mid x\notin B\}$.
• Para una información $o\in I\setminus\{\bot\}$, su conjunto de aristas es un subconjunto de $E$, denotado por $S_E(o)$, que satisface $S_E(o)\subseteq E$. Se establece que el conjunto de aristas del elemento neutro es vacío, es decir, $S_E(\epsilon)=\varnothing$.
• Para cualquier arista $e\in E$ del árbol, escribiendo $e=(u,v)$, existe una información $\iota(e)\in I$ asociada a $e$, cuyo conjunto de vértices son sus extremos y cuyo conjunto de aristas es ella misma: $S_V(\iota(e))=\{u,v\}$ y $S_E(\iota(e))=\{e\}$.

Hay dos formas de combinar información, denotadas por $R$ y $C$. Para cualesquiera $a,b\in I$, sean $r=R(a,b)$ y $c=C(a,b)$, con $r,c\in I$. Se cumple lo siguiente:

• Al combinar el elemento neutro con cualquier información se obtiene la otra información. Es decir, si $a=\epsilon$, entonces $r=c=b$; si $b=\epsilon$, entonces $r=c=a$.
• Al combinar información no válida con cualquier información se obtiene información no válida. Es decir, si $a=\bot$ o $b=\bot$, entonces $r=c=\bot$.
• En los casos restantes, si la intersección de los conjuntos de aristas de las dos informaciones no es vacía, o el tamaño de la intersección de sus conjuntos de vértices no es $1$, la combinación produce información no válida. Es decir, si $S_E(a)\cap S_E(b)\ne\varnothing$ o $|S_V(a)\cap S_V(b)|\ne1$, entonces $r=c=\bot$.

• En caso contrario,

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

  Aquí $\oplus$ denota la diferencia simétrica de conjuntos: $A\oplus B=(A\cup B)\setminus(A\cap B)$.

Se define la distancia entre dos vértices de $T$ como el número de aristas del único camino simple del árbol que tiene esos dos vértices como extremos.

Se da un parámetro de puntuación $M$ y $q$ consultas. Cada consulta proporciona un vértice $u$ del árbol y un entero no negativo $d$. Sea $X$ el conjunto de todos los vértices de $T$ cuya distancia a $u$ es como máximo $d$, y sea $Y=\{(a,b)\in E\mid a,b\in X\}$ el conjunto de aristas internas de $X$. Se puede demostrar que, partiendo de $\epsilon$ y de todas las $\iota(e)$ ($e\in E$), siempre se puede obtener, mediante un número finito de llamadas a $R,C$, una información $o\ne\bot$ que satisfaga $S_E(o)=Y$.

Para cada consulta debes construir una información $o$ que cumpla ese requisito, con un total de llamadas a $R$ y $C$ que no supere $M$. En particular, si $d=0$, basta con devolver directamente el elemento neutro $\epsilon$.

Detalles de implementación

Asegúrate de que tu programa comience con #include "count.h".

El archivo de cabecera count.h implementa lo siguiente:

1. Define el tipo de datos info, correspondiente a la información.
2. Define la constante emptyinfo, de tipo info, correspondiente a $\epsilon$. Puedes utilizarla directamente en tu programa.
3. Define e implementa las siguientes dos funciones de combinación de información, que puedes llamar directamente:

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

• Las dos funciones devuelven, respectivamente, la información correspondiente a $R(a,b)$ y $C(a,b)$.

Debes garantizar que el resultado de llamar a $R(a,b)$ o $C(a,b)$ no sea $\bot$; de lo contrario, el programa puede presentar un comportamiento anómalo.

1. Define e implementa una función para determinar si una información es el elemento neutro, que puedes llamar directamente:

bool isempty(info a);

• Esta función devuelve verdadero si y solo si $a$ es el elemento neutro.

Puedes consultar la biblioteca de interacción de referencia para conocer más detalles de implementación.

No necesitas ni debes implementar una función principal. Debes implementar las siguientes funciones:

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

• T indica el número del caso de prueba, n el número de vértices del árbol, q el número de consultas y M el parámetro de puntuación del caso de prueba.
• Tanto fa como e tienen longitud $n-1$. Para $0\le i<n-1$, fa[i] e $i+2$ son los dos extremos de la arista $e_i$; e[i] es el elemento de tipo info correspondiente a $\iota(e_i)$ mencionado en la descripción. Se garantiza que fa[i] es menor que $i+2$.

info ask(int u, int d);

• Se proporciona una consulta cuyos parámetros tienen el significado descrito en el enunciado. Al terminar la función debes devolver una información que cumpla los requisitos del problema.

En la evaluación final, para cada caso de prueba, la biblioteca de interacción llamará exactamente una vez a init y después llamará $q$ veces a ask. La biblioteca utilizará una implementación especial en la que cada variable de tipo info ocupará siempre 12 bytes de memoria, lo que difiere de la biblioteca de referencia proporcionada. Para que el uso de memoria se mantenga dentro del límite del problema, debes garantizar que no existan simultáneamente demasiadas variables de tipo info durante la ejecución.

Se garantiza que, si se respeta el límite de llamadas y no se llama a isempty, el tiempo de ejecución de la biblioteca de interacción de la evaluación final no supera $0.6$ segundos y la propia biblioteca no consume más de $16$ MiB de memoria. Se garantiza que, si se ejecutan únicamente $10^8$ llamadas a isempty, el tiempo de ejecución de la biblioteca de la evaluación final no supera $0.25$ segundos.

Los archivos proporcionados incluyen count.cpp, un programa de ejemplo que puedes utilizar como base para implementar la solución. También incluyen un archivo de respaldo count_backup.h, que se garantiza que es idéntico a count.h.

Cómo probar tu programa

El directorio del problema contiene dos implementaciones de referencia de la biblioteca de interacción, grader.o y checker.o, que son archivos enlazables obtenidos al compilar dos bibliotecas diferentes. La implementación utilizada en la evaluación final difiere de estas, por lo que tu solución no debe depender de la implementación concreta de la biblioteca de interacción, ni tampoco de la implementación concreta del tipo info en count.h.

Debes modificar el archivo count.h proporcionado para permitir el enlazado. Concretamente, al enlazar el código fuente count.cpp con grader.o, debes comentar la línea 5 de count.h y conservar la línea 4. Para enlazar con checker.o, debes comentar la línea 4 y conservar la línea 5. Puedes modificar por tu cuenta la implementación de count.h para compilar los distintos programas.

Después de modificarlo, puedes compilar un ejecutable en el directorio del problema con los siguientes comandos:

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

El primer comando compila el archivo actual count.cpp y lo enlaza con grader.o para generar el ejecutable count; el segundo compila count.cpp y lo enlaza con checker.o para generar el ejecutable count.

El ejecutable count obtenido de esta forma funciona así:

• Lee de la entrada estándar datos con el siguiente formato:
  • La primera línea contiene cuatro enteros $id,n,q,M$, que indican, respectivamente, el número del caso de prueba, el número de vértices, el número de consultas y el parámetro de puntuación.
  • La segunda línea contiene $n-1$ enteros $p_2,p_3,\ldots,p_n$, que indican los padres de los vértices del $2$ al $n$. Durante la depuración local debes garantizar que $\forall i\in[2,n],\ p_i<i$.
  • Las siguientes $q$ líneas contienen dos enteros $u,d$ cada una y describen una consulta.
• Después de leer los datos, la biblioteca realiza las pruebas. Si tu programa no cumple las restricciones de la biblioteca, se devuelve el mensaje de error correspondiente en la salida. En caso contrario, la salida del ejecutable enlazado es la siguiente:
  • Una línea con tres enteros $C_1,C_2,C_3$, donde:
    • $C_1$ es el número total de llamadas a funciones de la biblioteca realizadas por el programa dentro de init.
    • $C_2$ es el número total de llamadas a funciones de la biblioteca realizadas durante toda la ejecución del programa.
    • $C_3$ es el máximo número de llamadas a funciones de la biblioteca realizadas en una de las $q$ llamadas a ask.
    • Para estas tres estadísticas solo se cuentan las llamadas a MR y MC; no se cuentan las llamadas a isempty.
• Las comprobaciones que se pueden realizar también dependen del archivo enlazado:
  • grader.o: durante la ejecución no comprueba si la información devuelta por ask es correcta, pero ayuda a determinar si las operaciones de interacción cumplen los requisitos. Su tiempo de ejecución es el más próximo al de la biblioteca de evaluación, por lo que puedes utilizar este programa para medir la velocidad; sin embargo, no garantiza la corrección del programa.
  • checker.o: durante la ejecución comprueba si la información devuelta por ask es correcta y también ayuda a determinar si las operaciones de interacción cumplen los requisitos. Además, comprueba si la información devuelta por ask es correcta. Este programa permite comprobar la corrección de las respuestas.

Durante la depuración debes garantizar que los datos introducidos en el ejecutable count cumplan el formato de entrada anterior; de lo contrario, no se garantiza que los resultados de salida sean correctos.

Ejemplos

Ejemplo 1

Consulta count/count1.in y count/count1.ans en el directorio del participante.

Ejemplo 2

Consulta count/count2.in y count/count2.ans en el directorio del participante.

Este ejemplo cumple la propiedad especial A de las restricciones.

Ejemplo 3

Consulta count/count3.in y count/count3.ans en el directorio del participante.

Este ejemplo cumple la propiedad especial B de las restricciones.

Ejemplo 4

Consulta count/count4.in y count/count4.ans en el directorio del participante.

Subtareas

En la evaluación final solo se recogerá count.cpp. Modificar otros archivos del directorio del participante no afectará al resultado de la evaluación. Ten en cuenta lo siguiente:

• No se garantiza que una variable de tipo info sin inicializar sea emptyinfo.
• No intentes acceder a los miembros del tipo info ni modificarlos; hacerlo se considerará un ataque a la biblioteca de interacción.
• No llames a MR ni a MC antes de que se llame a init; de lo contrario, puede producirse un comportamiento indefinido.
• Solo puedes acceder a las variables que hayas definido y a las variables de tipo info devueltas por la biblioteca. Intentar acceder a otros espacios puede causar errores de compilación o de ejecución.

Este problema está sujeto, en primer lugar, a las mismas restricciones que los problemas tradicionales: por ejemplo, un error de compilación da 0 puntos en todo el problema; un error de ejecución, exceder el límite de tiempo o exceder el límite de memoria da 0 puntos en el caso de prueba correspondiente.

Además, si en un caso de prueba el programa realiza una llamada ilegal a una función o da una respuesta incorrecta a una consulta, obtiene 0 puntos en ese caso. En caso contrario, sean $C_1$ y $C_3$, respectivamente, el número de llamadas a funciones de la biblioteca dentro de init y el máximo número de llamadas a funciones de la biblioteca entre todas las $q$ llamadas a ask. Si $C_1\le3\cdot10^7$ y $C_3$ no supera el parámetro de puntuación $M$ del caso de prueba, obtienes los puntos de ese caso; de lo contrario, no obtienes sus puntos. Nota: al calcular $C_1,C_3$, solo se cuentan las llamadas a MR y MC, y no las llamadas a isempty.

Restricciones

Para todos los casos de prueba, $1\le n\le2\cdot10^5$ y $1\le q\le10^6$. En cada consulta, $1\le u\le n$ y $1\le d\le n-1$.

Propiedad especial A: se garantiza que, para todo $i\in[1,n-1]$, el padre del vértice $i+1$ es $i$.

Propiedad especial B: se garantiza que todas las consultas satisfacen $u=1$.

Propiedad especial C: se garantiza que todas las consultas satisfacen $d\le100$.

Propiedad especial D: se garantiza que todas las consultas satisfacen $d\ge1000$.