Comentário Problema Fortuna

Comentário por Murilo Maeda e Henrique Vianna

Conhecimentos Prévios

• Somas em Prefixo
• Binary Lifting
• Busca em Grafos
• Segment Tree com Lazy Propagation ou BIT

Esse é um problema relativamente complicado e descobrir a ideia final requer várias observações. Por isso, vamos comentar todas as parciais do problema, já que elas ajudam a resolver para 100 pontos.

Subtarefa 1: $M = 1$

Já que $M = 1$, haverá uma única reunião. Então, podemos simplesmente fazer uma $DFS$ a partir da anfitriã e ir marcando quem estiver dentro do intervalo estipulado.

Subtarefa 2: $B_i = i - 1$ para todo $i > 1$ – ou seja, a mãe da matriarca $i$ é a matriarca $i-1$

O que essa subtarefa quer dizer é que a árvore vai ser uma linha, ou seja, se tomarmos a matriarca 1 como raíz, todos os vértices (fora a única folha) vão ter exatamente 1 filho. Com isso temos basicamente um vetor no qual os valores das fortunas vão decrescendo conforme o índice aumenta.

Para resolver esse problema, vamos manter um vetor auxiliar $Resp$ de tamanho $N + 1$ que guarde no índice $i$ para quantas reuniões a matriarca $i$ foi convocada. Também vamos representar a árvore como um vetor $V$ que guarde na posição $i$ a fortuna $A_i$ da matriarca $i$. Outra observação importante é que uma convocação $j$ agora se resume a encontrar a matriarca de menor índice $i$ cuja fortuna seja menor ou igual a $D_j$ e a matriarca de maior índice $k$ cuja fortuna seja maior do que $E_j$.

Então, como o vetor está ordenado (do maior para o menor), basta fazermos duas buscas binárias: uma para encontrar a matriarca de maior fortuna que foi convocada e outra para encontrara a matriarca de menor fortuna que foi convocada e depois adicionar 1 no vetor $Resp$ de todo mundo entre essas duas (incluindo elas).

Para adicionar 1 em todos os elementos do vetor $Resp$, vamos usar um truque de somas parciais. Para esse truque, se quisermos adicionar 1 nos elementos do intervalo $[i,j]$, basta irmos no vetor $Sparcial$, que guarda as somas parciais de prefixo do vetor $Resp$, e somarmos 1 no índice $i$ e -1 no índice $j+1$. dessa forma, somente os elementos no intervalo que queremos serão afetados quando calcularmos a soma daquele intervalo usando somas parciais.

Para a resposta, basta pegar a soma parcial de cada matriarca individualmente.

Subtarefa 3: $E_j = 1$  e $D_j = A_{o_j}$

Ao que essa tarefa se resume é que todo mundo na subárvore da anfitriã vai ser vai ser chamada. Ou seja, para cada das reuniões que forem feitas, basta somar 1 no vetor de resposta de todo mundo que está na subárvore da anfitriã. Para fazer isso, podemos linearizar a árvore e utilizar o mesmo truque de somas parciais que usamos na parcial anterior.

Para linearlizar a árvore, podemos utlizar a técnica "Euler Tour". Para melhor compreensão, analise o código a seguir:

Na implementação acima, temos: $timer$ guarda o "tempo" atual da $dfs$, $tin[i]$ guarda o tempo em que se "entra" no vértice $i$ , ou seja, o valor de $timer$ quando $dfs(i, pai(i))$ foi chamada e $tout[i]$, que representa o tempo em que se "sai" do vértice $i$, ou seja, o maior valor de $tin[j]$ para algum $j$ na subárvore de $i$. Sendo assim, a subárvore de qualquer vértice pode ser representada por um intervalo continuo $(tin[i], tout[i])$, daí o nome "linearização".

Subtarefa 4: $D_j =A_{o_j}$ e $A_i \leq 200$

Note que nessa tarefa ainda mantemos a característica da subtarefa anterior de que quando uma reunião acontece, somente a subárvore da anfitriã é convidada. Mas, agora, a característica que não está presente é a de que todos vão ser chamados. Como isso acontece, não podemos mais utilizar o truque de somar 1 em todos os elementos do intervalo, já que podem haver "buracos" nos segmentos.

O que a outra condição que o enunciado nos dá, o limitante de fortuna, garante é que a altura máxima da árvore vai ser 200, já que há uma diferença de pelo menos 1 da fortuna de uma matriarca mais velha para outra mais nova. Então, podemos simplesmente marcar cada uma das anfitriãs e qual é o intervalo da reunião que elas fizeram. Para calcular a resposta pegamos um vértice por vez e subimos até a raiz, calculando para cada um dos vértices no caminho em quantas festas que ele foi anfitrião o vértice do qual nós partimos participou. Mas, note que, uma única matriarca pode ser anfitriã de várias festas com vários intervalos diferentes, então temos que encontrar uma maneira de guardar e checar a quais intervalos uma determinada fortuna pertence quando estamos subindo pela árvore.

Para fazer isso podemos simplesmente guardar um vetor de marcação para cada um dos vértices que indica para cada fortuna quantas festas ela participou com aquele vértice de anfitrião. Isto é, se um vértice $i$ é anfitrião de uma festa de intervalo $E_j$ e $D_j$, basta somarmos 1 no intervalo $[E_j,D_j]$ do vetor de marcação do vértice $i$. Quando formos calcular a resposta para um vértice $k$ de fortuna $A_k$ e estivermos passando pelo vértice $i$, somamos o número guardado no vetor de marcação do vértice $i$ na resposta do vértice $k$.

Subtarefa 5: Sem restrições adicionais

Para resolver o problema completamente deve-se perceber que é válido simplesmente “transferir” uma reunião de um vértice para o seu último ancestral que tem fortuna dentro do intervalo, ou seja, o ancestral $j$ de $O_i$ de menor profundidade na árvore que satisfaz $fortuna[j] \leq D_i$. Para achar esse ancestral rapidamente, basta usarmos a técnica de binary lifting. Chamaremos esse vértice de $T_i$. Tendo isso feito, para cada reunião $i$, só precisamos considerar os descendentes de $T_i$, não mais os ancestrais.  

Tendo isso feito, podemos finalizar o problema de diversas maneiras. O jeito mais prático é fazer uma $dfs$, mantendo alguma estrutura que permita somas e consultas (range sum, point query) em tempo logarítmico, como uma BIT ou uma Segment Tree. Pense nessas estruturas como um “vetor de frequência”, capaz de nos informar em quantas das reuniões que estão “ativas” (para um dado vértice $u$, por conta da $dfs$, só estarão “ativas” as reuniões que tem como $T_i$ um dos ancestrais de $u$ ou o próprio $u$) uma dada fortuna idade está contida. Quando “entrarmos” num vértice, somaremos, $1$ na nossa estrutura, no intervalo $[E_i, D_i]$ para toda reunião que tem como $T_i$ o nó atual. Para acharmos a resposta de um dado vertice $u$, basta fazermos uma consulta na estrutura,  obtendo a quantidade de reuniões em que está contida sua fortuna. Quando “sairmos” do nó, devemos desativar essas reuniões, subtraindo $1$.

Veja o código abaixo para melhor compreensão: