4083 - Cards of the Secret Society

Created by Reinier Rodríguez González
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 65000 MS | Test Time: 10000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Once upon a time, there existed a secret society of card collectors. Of course, the main goals of the society were not just to collect cards, but those were secret, so we know nothing about them. Today, the experts have decided to study all the information about this secret society, and the research reveals new details.

The society has a hierarchical structure. The principal member is the Grand Master. He has many apprentices, so he supervise them. Each apprentice of the Grand Master can has his own apprentices; the apprentices of the apprentices of the Grand Master can have their own apprentices, and so on. Every member of the society can have zero, one or more apprentices, and exactly one tutor, except for the Grand Master. For that reason, one person can be apprentice and tutor at the same time.

Each member of the society has a unique identifier composed by a sequence of five decimal digits (0...9). Therefore, a tutor is master of his apprentices, and the master of the tutor is master of the tutor’s apprentices too. The Grand Master is everybody's "master", except from himself.

Each member of the society has a single card. There are several kind of cards: some colored, some monochrome, some moderately big cards and some tiny cards. One member can owns a card identical to the card of other member. Each card has an identifier, which is a sequence of four capital characters (A...Z). Two identical cards have the same identifier and two different cards have different identifiers.

You have received the members list and the cards that each member owns. In addition, you know also the relations of tutorship between the members. An ancient member of the society has requested your services in order to find the answer a certain number of queries of the following type. Given the identifier of some member, you need to find the set of cards that he and all of his apprentices own.
  • Let’s call F the number of times that appears the most common card(s) on that set. Note that several cards can appear the same number of times, but that number of times has to be the maximum.
  • Let’s call C the number of cards that appears F times in the set, i.e., the most common cards.
For each query, you have to find the value of F * C (F times C).
Érase una vez una sociedad secreta de coleccionistas de tarjetas. Por supuesto, los objetivos principales de la sociedad no eran solo recolectar tarjetas, sino que eran secretas, por lo que no sabemos nada sobre ellas. Hoy los expertos han decidido estudiar toda la información sobre esta sociedad secreta y la investigación revela nuevos detalles.

La sociedad tiene una estructura jerárquica. El miembro principal es el Gran Maestro. Él tiene muchos aprendices, por lo que los supervisa. Cada aprendiz del Gran Maestro puede tener sus propios aprendices; los aprendices de los aprendices del Gran Maestro pueden tener sus propios aprendices, y así sucesivamente. Cada miembro de la sociedad puede tener cero, uno o más aprendices, y exactamente un tutor, excepto el Gran Maestro. Por esa razón, una persona puede ser aprendiz y tutor al mismo tiempo.

Cada miembro de la sociedad tiene un identificador único compuesto por una secuencia de cinco dígitos decimales (0...9). Por lo tanto, un tutor es el maestro de sus aprendices, y el maestro del tutor también es el maestro de los aprendices del tutor. El Gran Maestro es el "amo" de todos, excepto de sí mismo.

Cada miembro de la sociedad tiene una sola tarjeta. Hay varios tipos de cartas: algunas de color, otras monocromáticas, algunas moderadamente grandes y algunas pequeñas. Un miembro puede poseer una tarjeta idéntica a la tarjeta de otro miembro. Cada tarjeta tiene un identificador, que es una secuencia de cuatro letras mayúsculas (A...Z). Dos cartas idénticas tienen el mismo identificador y dos tarjetas diferentes tienen identificadores diferentes.

Usted ha recibido la lista de miembros y las tarjetas que posee cada miembro. Además, también conoces las relaciones de tutoría entre los miembros. Un antiguo miembro de la sociedad ha solicitado sus servicios para encontrar la respuesta a un determinado número de consultas del siguiente tipo. Dado el identificador de algún miembro, necesitas encontrar el conjunto de cartas que él y todos sus aprendices poseen.
  • Llamemos F a la cantidad de veces que aparece la(s) tarjeta(s) más común(es) en ese conjunto. Tenga en cuenta que varias tarjetas pueden aparecer la misma cantidad de veces, pero esa cantidad de veces tiene que ser el máximo.
  • Llamemos C a la cantidad de tarjetas que aparecen F veces en el conjunto, es decir, las cartas más comunes.
Para cada consulta, debe encontrar el valor de F * C (F por C).
Once upon a time, there existed a secret society of card collectors. Of course, the main goals of the society were not just to collect cards, but those were secret, so we know nothing about them. Today, the experts have decided to study all the information about this secret society, and the research reveals new details.

The society has a hierarchical structure. The principal member is the Grand Master. He has many apprentices, so he supervise them. Each apprentice of the Grand Master can has his own apprentices; the apprentices of the apprentices of the Grand Master can have their own apprentices, and so on. Every member of the society can have zero, one or more apprentices, and exactly one tutor, except for the Grand Master. For that reason, one person can be apprentice and tutor at the same time.

Each member of the society has a unique identifier composed by a sequence of five decimal digits (0...9). Therefore, a tutor is master of his apprentices, and the master of the tutor is master of the tutor’s apprentices too. The Grand Master is everybody's "master", except from himself.

Each member of the society has a single card. There are several kind of cards: some colored, some monochrome, some moderately big cards and some tiny cards. One member can owns a card identical to the card of other member. Each card has an identifier, which is a sequence of four capital characters (A...Z). Two identical cards have the same identifier and two different cards have different identifiers.

You have received the members list and the cards that each member owns. In addition, you know also the relations of tutorship between the members. An ancient member of the society has requested your services in order to find the answer a certain number of queries of the following type. Given the identifier of some member, you need to find the set of cards that he and all of his apprentices own.
  • Let’s call F the number of times that appears the most common card(s) on that set. Note that several cards can appear the same number of times, but that number of times has to be the maximum.
  • Let’s call C the number of cards that appears F times in the set, i.e., the most common cards.
For each query, you have to find the value of F * C (F times C).

Input specification

In the first line there is an integer N (1 <= N <= 10^5), the number of members that the society has. Then N lines will follow, each with a member identifier and a card identifier, separated by a single space. Each of these lines represent that the member with the left identifier owns a card with the right identifier. After that, N-1 lines will follow, each with two member identifiers, indicating that the first is the tutor of the second. Finally, you will be given a number of queries Q (Q <= N), followed by Q lines, each of them with a member identifier.
En la primera línea hay un número entero N (1 <= N <= 10^5), la cantidad de miembros que tiene la sociedad. Luego seguirán N líneas, cada una con el identificador de un miembro y el identificador de una tarjeta, separadas por un solo espacio. Cada una de estas líneas indica que el miembro con el identificador de la izquierda posee una tarjeta con el identificador de la derecha. Después, seguirán N-1 líneas, cada una con los identificadores de dos miembros, lo que indica que el primero es el tutor del segundo. Finalmente, se le dará el número de consultas Q (Q <= N), seguidas de Q líneas, cada una de ellas con el identificador de un miembro.
In the first line there is an integer N (1 <= N <= 10^5), the number of members that the society has. Then N lines will follow, each with a member identifier and a card identifier, separated by a single space. Each of these lines represent that the member with the left identifier owns a card with the right identifier. After that, N-1 lines will follow, each with two member identifiers, indicating that the first is the tutor of the second. Finally, you will be given a number of queries Q (Q <= N), followed by Q lines, each of them with a member identifier.

Output specification

For each of the last Q lines, you must print, in separate lines, a single integer with the answer to the task.
Para cada una de las últimas Q líneas, debe imprimir, en líneas separadas, un único entero con la respuesta a la tarea.
In the first line there is an integer N (1 <= N <= 10^5), the number of members that the society has. Then N lines will follow, each with a member identifier and a card identifier, separated by a single space. Each of these lines represent that the member with the left identifier owns a card with the right identifier. After that, N-1 lines will follow, each with two member identifiers, indicating that the first is the tutor of the second. Finally, you will be given a number of queries Q (Q <= N), followed by Q lines, each of them with a member identifier.

Sample input

6
11111 XXXX
22222 ABCD
33333 LUNA
44444 LUNA
44445 XXXX
64444 XXXX
11111 22222
11111 33333
33333 44444
33333 44445
33333 64444
3
11111
22222
33333

Sample output

3
1
4

Hint(s)