28a Olimpíada Brasileira de Informática
Submeta sua solução

Startup

Devido ao seu sucesso na primeira fase da OBI, a startup IOI (Insatisfação Observada International) te ofereceu uma entrevista de estágio. Como parte do processo seletivo, você deve ajudar a empresa a avaliar a satisfação dos funcionários com seus empregos. Na hierarquia da startup, cada funcionário (exceto o fundador) possui um chefe. A empresa valoriza experiência no trabalho: o chefe de todo funcionário entrou na empresa antes dele. Para cada funcionário, os seus subordinados diretos são os funcionários que têm ele como chefe. Cada funcionário possui um salário mensal, e um estudo feito pela empresa revelou que existe um jeito simples de descobrir quais funcionários estão insatisfeitos: um funcionário está insatisfeito se, e somente se, algum dos seus subordinados diretos ganha mais do que ele (note que ele está satisfeito se seus subordinados ganham tanto quanto ele). Com o fim do trimestre chegando, o time de Recursos Humanos está considerando ajustar os salários de alguns funcionários, possivelmente aumentando ou reduzindo o valor mensal (porém, para evitar confusão, eles podem alterar o salário de cada funcionário no máximo uma vez). Mas, primeiro, eles precisam avaliar a insatisfação geral dos funcionários durante essa série de ajustes. Sua tarefa é, dada a estrutura hierárquica da empresa, os salários iniciais, e a sequência considerada de ajustes, determinar o número total de funcionários insatisfeitos inicialmente e após cada ajuste.

Entrada

A primeira linha de entrada contém um inteiro N, indicando o número de funcionários da empresa. Os funcionários são identificados de 1 a N de acordo com a ordem em que entraram na startup. O fundador é identificado pelo número 1. Cada uma das N linhas seguintes descreve um funcionário: a linha i+1 contém dois inteiros, Ci e Si, indicando o chefe e o salário do funcionário i, respectivamente. É garantido que C1=1 (consideramos que o fundador é chefe de si mesmo) e que Cinão desfazemos o ajuste i-1 antes de fazer o ajuste i).

Saída

Seu programa deve produzir A+1 linhas, cada uma contendo um único inteiro. A primeira linha deve conter o número de funcionários insatisfeitos antes dos ajustes. As próximas A linhas devem conter os números de funcionários insatisfeitos após cada ajuste.

Restrições

  • 1 ≤ N ≤ 100 000
  • 0 ≤ A ≤ N
  • C1=1 e 1 ≤ Ci1
  • 1 ≤ Si ≤ 1 000 000
  • 1 ≤ I ≤ N
  • 1 ≤ X ≤ 1 000 000
  • Os valores de I são todos distintos entre si (ou seja, cada funcionário tem o salário ajustado no máximo uma vez).

Informações sobre a pontuação

A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:
  • Subtarefa 1 (25 pontos): N ≤ 100 e A=0 -- ou seja, nenhum ajuste será feito, e você só precisa calcular a insatisfação total inicial. (Veja o exemplo de entrada 1.)
  • Subtarefa 2 (25 pontos): N ≤ 2 000.
  • Subtarefa 3 (25 pontos): Cada funcionário tem no máximo 2 subordinados diretos.
  • Subtarefa 4 (25 pontos): Nenhuma restrição adicional.
Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (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 qualquer uma das suas submissões.

Exemplos

Entrada
7
1 300
1 350
1 200
3 150
3 250
2 350
3 100
0
Saída
2
	

 

Entrada
5
1 500
1 400
2 300
3 450
4 300
2
4 300
3 500
Saída
1
0
1
	

 

Entrada
6
1 100
1 200
1 300
2 400
3 500
3 600
3
1 500
3 550
4 200
Saída
3
2
3
2
	

 

PJ P1 P2 PS
Tarefas Programação Nível 1
Promoção
Patrocínio
Apoio
Coordenação