|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #33Ended |
H - Feliz árbol pequeño
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Kappa tiene un feliz árbol pequeño con raíz y $n$ nodos. El amigo de Kappa, Keepo, tiene un nodo favorito en este árbol. A Kappa no le importa dejar jugar a Keepo con su árbol, pero este tiene que seguir sus reglas: él permite a Keepo recorrer el árbol solamente en preorden (DFS - depth-first search). Además, los nodos están numerados de $0$ a $n - 1$, y cada nodo tiene un color blanco o negro. Esto también limita la forma de recorrer el árbol. A continuación se muestra el pseudocódigo usado:
$\verb|DFS(tree T):|$
$\verb| visit T’s root u|$
$\verb| if(u is white):|$
$\verb| for(all u’s child v, in ascending order by their index):|$
$\verb| DFS(subtree rooted at v)|$
$\verb| else:|$
$\verb| for(all u’s child v, in descending order by their index):|$
$\verb| DFS(subtree rooted at v)|$
La raíz está numerada con $0$, y cada nodo diferente a la raíz tiene un número mayor que su padre. A Keepo le gusta más el nodo $n - 1$, pero él no quisiera pasar mucho tiempo recorriendo el árbol. Por lo tanto, Keepo te pide que lo ayudes a determinar la cantidad de nodos que debe visitar antes de alcanzar su nodo favorito. Lo que hace las cosas más complicadas es que Kappa y Keepo cambian de idea frecuentemente. Algunas veces Kappa decide cambiar el color de todos los nodos en un subárbol, algunas veces Keepo cambia su nodo favorito. Luego de cada cambio, tú debes decirle a Keepo la nueva respuesta.
Input
La primera línea de la entrada contiene un entero $n$ $(1 \leq n \leq 10^5)$, el número de nodos. Al inicio, todos los nodos son blancos. La segunda línea contiene $n - 1$ enteros $p_1, p_2, ..., p_{n-1}$. $p_i$ $(0 \leq p_i \lt i)$ es el número que identifica al padre del nodo $i$. La tercera línea contiene $q$ $(1 \leq q \leq 10^5)$ enteros, el número de cambios. Las siguientes $q$ líneas representan un cambio cada una. En cada línea, hay un caracter y un número $u$ $(1 \leq u \lt n)$. Si el caracter es $\texttt{`a'}$, significa que Kappa cambia el color de todos los nodos en el subárbol con raíz en $u$. Si el caracter es $\texttt{`e'}$, significa que Keepo cambia su nodo favorito a $u$.
Output
La primera línea contiene el número de nodos que se deben visitar antes del nodo $n - 1$. Las siguientes $q$ líneas contienen la nueva respuesta despues de cada cambio.
Sample test(s)
Input
4
0 0 1
2
a 0
e 2
Output
2
3
1