Viaje a la Fiesta


Submit solution

Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Hay n ciudades numeradas desde 1 hasta n en Bytelandia. La primera ciudad es la capital. Existen n-1 rutas de autobuses: para cada ciudad i<>1, hay un bus que va de esta ciudad a la ciudad p_i (p_i < i), exactamente en esa dirección.

Existen m tipos de platos nacionales numerados desde 1 hasta m. Cada ciudad tiene un plato especial a_i, así que este y sólo este plato se puede comprar allí. Cada plato a_i es de uno de los tipos de 1 a m.

Hay c amigos numerados de 1 a c. El i^{th} amigo está actualmente en la ciudad v_i. Los amigos quieren celebrar una fiesta, por lo que necesitan reunirse en una ciudad. Obviamente, siempre es posible, pero quieren reunirse tan pronto como sea posible. Viajar en autobús toma una unidad de tiempo.

Ellos quieren comprar algunos platos para la fiesta siguiendo algunos requisitos:

  1. Cada amigo debe comprar una cantidad igual de platos.

  2. No debe haber dos tipos iguales de platos en la fiesta.

  3. Cada amigo puede comprar solo los tipos de platos que corresponden a las ciudades que visitó.

Necesitas responder q consultas (query en inglés). Cada consulta tiene la siguiente forma.Para cada consulta, debe calcular el número máximo posible de platos en la fiesta.

Dado tres enteros n,m y q, imprima la respuesta para cada consulta en una línea. Los valores p_i, a_i y los detalles de la consulta deben tomarse de la entrada estándar como se describe en la sección de formato de entrada.

Entrada

La primera línea de la entrada contiene tres enteros separados por espacio: n, m y q. La segunda línea contiene n-1 enteros separados por espacio p_2, ..., p_n. La tercera línea contiene n enteros separados por espacio: a_1, ..., a_n. La i^{th} de las siguientes q lineas contienen la descipcion de la i^{th} consulta. Cada consulta tiene el siguiente formato: un entero c y entonces c enteros v_1, ...,v_c separados entre si por un espacio.

Restricciones

  • 2 \leq n \leq 3.10^5
  • 1 \leq m \leq 1000
  • 1 \leq q \leq 5.10^4
  • 1 \leq p_i < i
  • 1 < \leq a_i \leq m
  • 2 \leq c \leq 5
  • 1 \leq v_i \leq n

Salida

Imprima q lineas. La i-esima linea debe contener un entero simple denotando la respuesta de la i-esima consulta.

Ejemplo # 1 de Entrada

5 3 4
1 2 2 1
2 3 1 3 1
2 3 4
3 5 2 2
4 3 4 2 5
2 2 2

Ejemplo # 1 de Salida

2
3
0
0

Explicación

En la primera consulta, hay dos amigos. El primero esta en la ciudad 3 y el segundo en la ciudad 4. Ellos se reuniran en la ciudad 2. Asi que el primero puede comprar un plato del tipo 1 en la ciudad 3 y el segundo puede comprar un plato del tipo 3 en la ciudad 4.

En la segunda consulta, hay tres amigos. El primero esta en la ciudad 5, el segundo en la ciudad 2 y el tercero esta en la ciudad 2. Ellos se encontraran en la ciudad 1. Asi, el primero puede comprar un plato de tipo 1 en la ciudad 5, el segundo puede comprar un plato de tipo 3 en la ciudad 2 y el tercero puede comprar un plato de tipo 2 en la ciudad 1.

En la tercera consulta, hay cuatro amigos, pero no hay manera de comprar algunos platos ya que hay 3 tipos de platos y 3 < 4. En la ultima consulta, hay dos amigos en la misma ciudad, asi, que obviamente no hay manera de comprar algunos platos.

Ejemplo # 2 de Entrada

11 6 3
1 2 2 4 5 4 5 8 9 4
5 6 1 1 2 3 2 3 4 5 2
3 3 10 8
4 6 5 10 10
2 9 6

Ejemplo # 2 de Salida

6
4
2

Comments

There are no comments at the moment.