A família Silva tem a tradição de investir em grandes empreendimentos. A família é um matriarcado, ou seja, são as mulheres da família que comandam as decisões. Vamos chamar de matriarca cada mulher integrante da família. Elas são sócias de empresas como bancos, mineradoras, construtoras e petroleiras. Além de saberem analisar muito bem diversos setores da economia, elas são muito unidas e investem sempre de maneira conjunta, em família.
Apesar de investirem juntas, cada matriarca da família possui sua própria fortuna e administra seu próprio patrimônio. Um detalhe curioso é que, nessa família, a fortuna de uma matriarca é sempre menor que a fortuna de sua mãe, como consequência da experiência administrativa dos mais velhos.
Toda vez que uma matriarca da família pretende investir em algum empreendimento novo, ela convoca uma reunião com outras matriarcas para compartilhar conhecimento. Quando uma matriarca convoca uma reunião, ela define um intervalo de valores de fortunas, de modo que são convocadas todas as matriarcas da família que satisfazem as seguintes condições:
Por exemplo, considere a família mostrada na figura ao lado, com 10 matriarcas, identificadas pelos números de a , com sendo a matriarca mais velha.
A fortuna de cada matriarca está indicada ao lado dela, em milhões de reais.
Se a matriarca 2 convocar uma reunião e definir o intervalo de fortunas como , as matriarcas convocadas serão 1, 2, 3, 5, 6, 8 e 9.
Observe que a matriarca 4 não será convocada pois possui fortuna igual a 3 (menor do que o limite inferior ).
Por outro lado, uma reunião convocada pela matriarca 8 com o intervalo de fortunas terá as matriarcas 2, 6, 8 e 9.
Apesar de a matriarca 5 possuir fortuna no intervalo , ela não foi convocada pois não possui relação de parentesco direto com nenhuma outra matriarca convocada.
Sua tarefa é: dada a estrutura da família, a fortuna de cada matriarca, e quem convocou e os limites de fortuna de cada reunião, determine para quantas reuniões cada matriarca foi convocada.
A primeira linha de entrada contém dois inteiros e representando o número de matriarcas da família e o número de reuniões, respectivamente. As matriarcas da família são identificadas por inteiros de a , com o número representando a matriarca mais velha da família.
As próximas linhas descrevem a estrutura da família. A -ésima dessas linhas contém dois inteiros e representando a fortuna da -ésima matriarca e o identificador de sua mãe, respectivamente. A matriarca mais velha da família (matriarca 1) é a única matriarca com . É garantido que a fortuna de uma matriarca é sempre menor que a fortuna de sua mãe.
As próximas linhas descrevem as reuniões. A -ésima dessas linhas contém três inteiros , e , indicando que a matriarca foi anfitriã de uma reunião com intervalo de fortunas .
Seu programa deverá imprimir uma única linha contendo inteiros separados por espaços. O -ésimo desses números deve ser a quantidade de reuniões para as quais a matriarca foi convocada.
A tarefa vale pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:
Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.
10 2
10 1
8 1
5 5
3 1
6 1
4 8
1 5
7 2
5 8
2 8
2 4 10
8 4 91 2 1 0 1 2 0 2 2 0Explicação do exemplo 1: Este exemplo corresponde ao exemplo mostrado no enunciado.
8 5
42 1
31 1
29 2
27 3
18 4
15 5
12 6
5 7
1 17 42
4 18 30
8 5 28
4 16 40
6 12 181 2 3 4 5 2 2 1Explicação do exemplo 2: A seguir temos uma visualização da estrutura da família:
