Este es un problema interactivo.

La gran científica 欣 se dispone a construir una inteligencia artificial fuerte llamada 隆 para dominar el mundo. Tras introducir algunos problemas vietnamitas de competiciones de algoritmos como conjunto de entrenamiento, descubre que 隆 ha generado automáticamente un nuevo problema y ha proporcionado una solución. Además, 隆 ha reducido el 30 % de los datos de entrada del conjunto de prueba a este problema.

欣 se apresura a copiar el problema:

Dado un árbol con raíz, hay que admitir dos operaciones:

• Consultar la suma de los elementos de un camino del árbol.
• Cambiar el padre de un vértice por otro vértice.

«Este problema no parece tan potente; ¿por qué permite resolver el 30 % de los problemas del conjunto de prueba?», piensa 欣.

Antes de cerrar la página de resultados del entrenamiento, 欣 descubre de repente que, en el problema propuesto por 隆, el coste de combinar información no es $O(1)$.

欣 reflexiona y descubre que no sabe resolver este problema.

Para averiguar su dificultad, 欣 le presenta el problema a usted.

Descripción

Debe mantener un árbol con raíz en $1$. El árbol tiene $n$ vértices. Inicialmente, para todo $2 \le i \le n$, el vértice $i$ tiene un padre $p_i$, y se garantiza que $p_i \lt i$.

Al principio dispone de $n$ conjuntos $\{1\},\{2\},\cdots,\{n\}$. Para cualesquiera dos conjuntos $A$ y $B$, si $A \cap B=\varnothing$, puede obtener el conjunto $A \cup B$ mediante una operación con coste $|A|+|B|$.

Después se realizan $q$ operaciones. Cada operación es de uno de los dos tipos siguientes:

• 0 a b: sea $S$ el conjunto de vértices del camino entre $a$ y $b$ en el árbol. Debe expresar $S$ como $\cup_{i=1}^{k}A_i$, donde cada $A_i$ sea un conjunto que ya haya obtenido y $\forall i \neq j,A_i \cap A_j=\varnothing$. El coste de responder una consulta con $(A_1,A_2,\cdots,A_k)$ es $k$.
• 1 a b: cambia el padre del vértice $a$ a $b$. Se garantiza que $a \gt 1$ y que, tras el cambio, los $n$ vértices siguen formando un árbol, pero no se garantiza que $a \gt b$. Durante esta operación puede generar nuevos conjuntos para responder a consultas posteriores.

Sea $C_1$ el coste total consumido durante toda la ejecución del programa y $C_2$ el máximo coste consumido en una sola operación. Cada subtarea asigna puntos según los valores de $C_1,C_2$ de una forma determinada.

Detalles de implementación

Asegúrese de incluir #include "long.h" al principio de su programa.

El archivo de cabecera define el tipo de datos infoset, que almacena los conjuntos que haya obtenido.

Este tipo incluye la función miembro size(), que indica el tamaño del conjunto. La cabecera también proporciona la constante emptyset, que representa el conjunto vacío.

Además, puede llamar a las siguientes funciones:

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

• Genera un nuevo conjunto $A \cup B$ con el coste correspondiente.
• Puede generar repetidamente el mismo conjunto, pero el coste se contabiliza en cada ocasión.

void report(infoset A);

• Solo puede llamar a esta función durante una operación de consulta. Indica que añade un conjunto $A$ a la unión final con coste $1$.

No necesita ni debe implementar la función principal. Debe implementar las siguientes funciones:

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

• Puede preprocesar información antes de que comiencen las $q$ operaciones.
• El coste consumido en esta función no se incluye en el máximo coste consumido en una sola operación, pero sí en el coste total consumido durante toda la ejecución del programa.
• id es el número de la subtarea, n el número total de vértices y q el número total de operaciones.
• El tamaño de dad es $n-1$, y dad[i] indica el padre inicial del vértice $i+2$.
• El tamaño de ve es $n$, y ve[i] representa el conjunto inicial $\{i+1\}$.

void modify(int x,int y);

• Realiza una modificación que establece el vértice $y$ como padre del vértice $x$.

void ask(int x,int y);

• Realiza una consulta sobre la información del camino de $x$ a $y$ en el árbol.
• Debe llamar a report varias veces para responder. Al finalizar la consulta, la biblioteca de interacción comprueba si todos los conjuntos $A$ comunicados satisfacen las condiciones.

Durante la evaluación, la biblioteca llama primero una vez a init y después a modify y ask un total de $q$ veces.

Se garantiza que la forma del árbol y las operaciones que se realizarán están completamente determinadas antes de comenzar la interacción, y no se construyen dinámicamente según la interacción con su programa. Por tanto, las operaciones interactivas del problema son deterministas y no necesita preocuparse por su implementación concreta en la biblioteca.

Durante la evaluación, la biblioteca utiliza una implementación especial: cada variable de tipo infoset consume siempre $8$ bytes de memoria. Asegúrese de que no existan simultáneamente demasiadas variables de tipo infoset durante la ejecución.

Se garantiza que, respetando el límite de llamadas, el tiempo requerido por la biblioteca no supera los $2$ segundos; la memoria consumida por la propia biblioteca no supera los $16$ MB.

Cómo probar el programa

El archivo grader.cpp distribuido es una implementación de referencia de la biblioteca de interacción. La implementación utilizada en la evaluación final es diferente, por lo que su solución no debe depender de los detalles de implementación de la biblioteca.

Debe compilar el ejecutable con el siguiente comando:

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

Para el ejecutable obtenido:

• El ejecutable lee de la entrada estándar datos con el formato siguiente:
  • La primera línea contiene un entero $id$, el número de la subtarea.
  • La segunda línea contiene dos enteros $n,q$, el número total de vértices y de operaciones.
  • La tercera línea contiene $n-1$ enteros, los números de los padres de los vértices del $2$ al $n$, respectivamente.
  • Las siguientes $q$ líneas contienen tres enteros $op,x,y$ cada una, que describen una operación. $op=0$ indica una consulta y $op=1$ una modificación.
• Tras leer los datos, la biblioteca llama exactamente una vez a init y $q$ veces a modify o ask, utilizando los datos de entrada para probar sus funciones. Si el programa se ejecuta normalmente, imprime varias líneas, cada una con varios números que representan su respuesta a cada consulta. La última línea contiene dos enteros $W_1,W_2$, que indican, respectivamente, el coste total de ejecución de su programa y el máximo coste de una sola operación.

Los archivos distribuidos incluyen cuatro conjuntos de archivos de ejemplo; el cuarto satisface la propiedad especial de la subtarea dos. Al probar los ejemplos, ignore la comparación de la última línea de los archivos de salida, ya que esta línea indica el coste de ejecución del programa y no el resultado de una consulta.

Subtareas

Este problema está sujeto, en primer lugar, a las mismas restricciones que un problema tradicional. Por ejemplo, un error de compilación hace que el problema completo reciba $0$ puntos; un error de ejecución o superar los límites de tiempo o memoria hace que el caso de prueba correspondiente reciba $0$ puntos. Solo puede acceder a las variables que usted defina o que proporcione la biblioteca, y a sus espacios de memoria correspondientes. Intentar acceder a otros espacios puede provocar errores de compilación o ejecución.

Además de las condiciones anteriores, si en un caso de prueba su programa realiza una llamada ilegal a una función, no termina normalmente o responde incorrectamente a una consulta, ese caso recibe $0$ puntos. En caso contrario, hay dos métodos de puntuación basados en el coste consumido:

• Método de evaluación uno: si $W_1 \gt 6 \cdot 10^8$, el caso recibe $0$ puntos. En caso contrario, su puntuación es $\frac{\frac{1.5 \cdot 10^8}{\max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10}$ multiplicado por la puntuación de la subtarea a la que pertenece el caso.
• Método de evaluación dos: si $W_2 \gt 2 \cdot 10^4$, el caso recibe $0$ puntos. En caso contrario, su puntuación es $\frac{5000}{\max(W_2,5000)}$ multiplicado por la puntuación de la subtarea a la que pertenece el caso.

Las distintas subtareas utilizan distintos métodos de evaluación. La puntuación de una subtarea es la mínima puntuación entre todos sus casos de prueba.

Restricciones

Se garantiza que, en todos los casos de prueba, $1 \le n,q \le 10^5$.

Propiedad especial: se garantiza que, en todo momento, cada vértice distinto del vértice $1$ tiene como máximo un hijo.

Epílogo

欣 descubre que usted sigue sin resolver el problema después de cinco horas y queda muy satisfecha con las capacidades de 隆. Sin embargo, al levantarse a la mañana siguiente, descubre de repente que la demostración de complejidad de la solución de 隆 es incorrecta.