COCI 2006 - lubenica

Autor da análise: gabrielrcpgabrielrcp

http://www.hsin.hr/2006/final/second_day/tasks.pdf

Resumo

Dada uma árvore com $n$ vértices ($n \leq 10^5$), com uma função custo para suas arestas. E dados $k$ pares de vértices ($k \leq 10^5$), devemos determinar o custo mínimo e o máximo de uma aresta no único caminho entre cada um desses pares.

Solução

Antes de começar, eu recomendo fortemente a leitura desse tutorial do topcoder. A solução que eu vou descrever é apenas uma adaptação simples de um dos algoritmos descritos lá.

Para não ficar me repetindo o tempo todo, eu vou descrever apenas como encontrar o custo mínimo de uma aresta entre dois vértices. O máximo pode ser encontrado da mesma forma, mas trocando mínimos por máximos.

Como temos muitos queries, vamos fazer algum preprocessamento na árvore, para depois poder responde-los rapidamente.

Preprocessamento

A primeira coisa que vamos fazer depois de ler a árvore, é escolher uma raiz para ela. Eu escolhi sempre o vértice 0. Depois vamos calcular um vetor $\textrm{pai} [ 0 \ldots n-1 ]$, onde $\textrm{pai} [0] = 0$ e $\textrm{pai} [i]$ é o ancestral do vértice $i$. Isso pode ser calculado em $\mathcal O (n)$ com qualquer busca. Guarde ainda um vetor $\textrm{dist} [0 \ldots n-1]$, onde $\textrm{dist} [i]$ é a distância (em número de arestas, sem considerar os custos) de $i$ até a raiz, ou ainda o "nível" de $i$ na árvore.

Feito isso, vamos calcular duas matrizes $n \times \log n$, chamaremos elas de $\textrm{AC}$ e $\textrm{mini}$. $\textrm{AC}[i][j]$ será o ancestral de $2^j$ gerações de $i$ e $\textrm{mini}[i][j]$ é o custo mínimo de uma aresta no caminho entre $i$ e $\textrm{AC}[i][j]$.
Ambas podem ser calculadas em tempo $\mathcall O (n \log n )$ através da seguinte recorrência:

(1)
\begin{align} \textrm{AC}[i][j] = \begin{cases} \textrm{pai[i]} & \mbox{se } j = 0 \\ \textrm{AC}[ \textrm{AC}[i][j-1]][j-1] & \mbox{se } j > 0 \end{cases} \end{align}
(2)
\begin{align} \textrm{mini}[i][j] = \begin{cases} + \infty & \mbox{se } i = 0 \\ \textrm{custo} (i, \textrm{pai}[i]) & \mbox{se } j = 0 \mbox{ e } i \neq 0\\ \min \left( \textrm{mini}[i][j-1], \textrm{mini}[\textrm{AC}[i][j-1]][j-1] \right) & \mbox{c.c.} \end{cases} \end{align}

Processando as queries

Vamos chamar os dois vértices de uma query de $i$ e $j$. Seja $\textrm{LCA}(i,j)$ o ancestral comum de $i$ e $j$ com o maior valor de dist. O menor custo de uma aresta entre $i$ e $j$ será o mínimo entre o menor custo entre uma aresta entre $i$ e $\textrm{LCA}(i,j)$ e o menor custo entre uma aresta entre $j$ e $\textrm{LCA}(i,j)$.

Nós vamos encontrar o mínimo enquanto procuramos o $\textrm{LCA}(i,j)$. Vamos supor, sem perda de generalidade, que $\textrm{dist}[i] \geq \textrm{dist}[j]$.

Primeiro vamos fazer $i$ "subir" na árvore, até ficar no mesmo "nível" que $j$. Para isso, escreva $l = dist[i] - dist[j]$ como soma de potências de 2. E para cada potência de 2 que aparecer nessa soma, faça $i \gets AC[i][\mbox{ expoente da pot\^encia de 2 que apareceu }]$. Cada vez que você fizer essa operação, guarde numa variável resp o mínimo dos custos dos $\textrm{mini}[i][t]$ que você percorreu.

Agora $\textrm{dist}[i] = \textrm{dist}[j]$. Se $i = j$, então $\textrm{LCA}(i,j) = j$, aí é só devolver o valor de resp.

Caso contrário, encontre o maior valor $k$ tal que $\textrm{AC}[i][k] \neq \textrm{AC}[j][k]$.

Se não existir tal $k$, então $i$ e $j$ são filhos do mesmo pai, daí a resposta será o mínimo entre resp e os custo das arestas $(i, \textrm{pai}[i])$ e $(j, \textrm{pai}[j])$.

Se o valor de $k$ estiver bem definido, atualize resp como o mínimo entre resp, $\textrm{mini}[i][k]$ e $\textrm{mini}[j][k]$ e atualize os valores de $i$ e $j$ para $\textrm{AC}[i][k]$ e $\textrm{AC}[j][k]$.

Repita isso até que você ache a resposta. Uma observação importante é que os valores de $k$ são estritamente decrescentes. Assim você pode matar essa parte com um for só.

Complexidade

Fizemos um preprocessamento $\mathcal O (n \log n)$ e cada query é respondida em $\mathcal O (\log h)$, onde $h$ é a altura da árvore. Como não sabemos nada sobre a estrutura das árvores dos casos de teste, o máximo que podemos dizer é que $h < n$ e concluir que cada query é respondida em $\mathcal O (\log n)$

Testes

Entrada

5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
7
3 6 4
1 7 1
1 3 2
1 2 6
2 5 4
2 4 4
5
6 4
7 6
1 2
1 3
3 5
9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3

Saída

100 200
50 150
50 100
2 6
1 4
6 6
2 2
2 6
1 2
2 4
1 5
2 2
1 4

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License