Solução por Pedro Racchetti
Conhecimentos prévios necessários:
Nesse problema, podemos representar a Nlogônia como uma árvore, onde temos que encontrar uma vértice $$x$$, utilizando as perguntas descritas no enunciado.
Primeiro, podemos enraizar a árvore na cidade $$1$$, achando a distância de todos as cidades até $$1$$ com uma DFS. Podemos então perguntar a distância de $$1$$ até o tesouro. Chame essa distância de $$d$$. Se $$d$$ for $$0$$, sabemos que a resposta é $$1$$, e podemos encerrar o problema. Caso contrário, podemos então encontrar todas as cidades com distância $$d$$ de $$1$$, e armazená-las em um vetor, ordenado pela ordem em que a DFS os alcança.
Como esse vetor está ordenado, podemos aplicar uma espécie de busca binária, da seguinte maneira:
Suponha que estamos testando no intervalo $$[l, r]$$. Testaremos a cidade $$k$$ de índice $$m$$ no vetor, onde $$m = (l+r)/2$$.
Podemos perguntar “$$?$$ $$1$$ $$k$$”, que irá nos resultar uma distância $$2L$$. Temos então dois casos:
- $$2L = 0$$ Nesse caso, $$k = x$$. Isso acontecerá ao menos uma vez na busca binária;
- $$2L \neq 0$$ Nesse caso, podemos encontrar com Sparse Table as cidades $$u$$ e $$v$$, tal que $$u$$ é a $$(L – 1)$$-ésima cidade no caminho entre $$k$$ e $$x$$ e $$v$$ é $$L$$-ésimo cidade no caminho entre $$k$$ e $$x$$, além de ser o LCA entre essas duas cidades, já que como $$x$$ e $$k$$ estão na mesma distancia de $$1$$, a distância entre $$x$$ e $$v$$ deve ser igual à distância entre $$k$$ e $$v$$
Finalmente, podemos perguntar “$$?$$ $$2$$ $$v$$” tendo como resposta $$p$$. Se $$p$$ vêm antes de $$u$$ na ordem da DFS, podemos mover o intervalo para $$[l, m-1]$$. Caso contrário, movemos o intervalo para $$[m+1, r]$$.
Portanto, o número máximo de perguntas é $$2*log_2(n)+1$$, que é menor que $$36$$.
Complexidade: $$O(n*log_2(n))$$
Segue o código, para melhor compreensão:
https://gist.github.com/PedroRacchetti/ff357dcf5c00c93e690e8fb331c129b1
Note que existem outras soluções para esse problema que utilizam outros conceitos, como decomposição em centroides e Heavy-Light Decomposition.