Consultas de acessibilidade em uma árvore em

Recebi uma árvore não direcionada no sentido teórico usual dos grafos. Dado um vértice um incidente de edge em , preciso responder a consultas do formulário retornando qualquer folha de que seja alcançável de com um caminho incluindo e nenhuma outra borda incidente para ? Mais informalmente, a restrição é que, quando a vantagem é dada, só podemos prosseguir nessa direção.$T$$v$$(v,u)$$v$$T$$v$$(u,v)$$v$

Eu posso simplesmente executar um DFS e retornar uma folha encontrada. Eu acho que isso levaria tempo, onde é o diâmetro da . No entanto, gostaria de responder a uma consulta em time. Além disso, gostaria apenas de permitir um tempo linear de pré-processamento. Minha idéia para conseguir isso foi usar um DFS, rotular folhas e rotular bordas quando a pesquisa retornar. Essa ideia pode funcionar com algum esforço adicional, mas não tenho muita certeza dos detalhes.$O(d)$$d$$T$$O(1)$

A "acessibilidade dos gráficos" apresentou alguns resultados, mas talvez eles estejam lidando com problemas mais complexos. Estou feliz com qualquer método que use tempo de pré-processamento e responda às consultas no tempo .$O(n+m)$$O(1)$

Sim, acho que você pode fazer isso em $O(1)$Tempo. Descrevo um método abaixo. Provavelmente existe uma maneira mais simples de fazer isso, mas o seguinte deve ser suficiente.

Pré-processando. Suponho que podemos ver sua árvore como uma árvore enraizada, com alguma raiz. No pré-processamento, anote cada nó interno$w$ com um exemplo de uma folha que é descendente de $w$. Isso pode ser feito em$O(n+m)$ tempo de pré-processamento, usando uma travessia descendente (DFS) muito simples.

Além disso, defina $p^*(\cdot)$ recursivamente da seguinte maneira: se $w$ tem irmãos, então $p^*(w)=w$; de outra forma,$p^*(w)=p^*(v)$ Onde $v$ é o pai de $w$; e$p^*(r)=r$, Onde $r$ é a raiz de $T$. Em inglês,$p^*(w)$ é definido como o nó obtido começando em $w$e continuando para cima até chegarmos a um nó que tem dois ou mais filhos (ou a raiz). No pré-processamento, calcularemos o valor de$p^*(w)$ para cada nó $w$ e armazene-o associado a $w$. Isso também pode ser calculado em$O(n+m)$ Tempo.

Respondendo a uma consulta. Agora, veja como responder à consulta, retorne qualquer folha que seja acessível a partir de$v$ com um caminho incluindo $(u,v)$, e nenhuma outra aresta incidente na $v$:

• Caso 1: suponha $u$ é filho de $v$. Em seguida, responder à sua consulta equivale a retornar qualquer folha descendente de$u$. Isso pode ser feito em$O(1)$ tempo usando a anotação em $u$.

• Caso 2: suponha $u$ é o pai de $v$e $u$tem pelo menos um outro filho. Então, olhe para qualquer outro filho de$u$, chame-o $w$. Em seguida, responder à sua consulta equivale a retornar qualquer folha descendente de$w$. Isso pode ser feito em$O(1)$ tempo usando a anotação em $w$.

• Caso 3: suponha $u$ é o pai de $v$e $u$não tem outros filhos. Então deixa$u'=p^*(u)$ e deixar $w$ ser qualquer outro filho de $u'$ (não um ancestral de $v$) Em seguida, responder à sua consulta equivale a retornar qualquer folha descendente de$w$. Isso pode ser feito em$O(1)$ tempo usando a anotação em $w$.

Nos três casos, a resposta à consulta pode ser calculada em $O(1)$ Tempo.