Solução por Pedro Racchetti
Conhecimentos utilizados:
Para esse problema, primeiro temos que perceber que para qualquer caminho, podemos simplesmente usar o menor ancestral comum (LCA) entre os dois extremos, se considerarmos a raiz como um nó qualquer (iremos usar o $$1$$, a título de implementação).
Podemos então perceber que se considerarmos a sub-árvore do LCA $$X$$ de um caminho, e algum outro caminho com o LCA $$Y$$ de altura menor que a altura de $$X$$, e um dos pontos extremos de $$Y$$ estiver na sub-árvore de $$X$$, não precisamos incluir $$X$$ no conjunto resposta! Portanto, quando processarmos um caminho, podemos verificar se qualquer um dos dois extremos já foram marcados. Se não, inserimos o LCA no conjunto resposta, e marcamos todos os vértices da sub-árvore dele.
Esse algoritmo porém fica muito demorados. Para acelerá-lo, podemos linearizar a árvore da seguinte maneira: guardaremos uma variável $$timer$$. Sempre que chamarmos uma nova recursão na DFS na vértice $$f$$, incrementamos o $$timer$$ por 1, e guardaremos esse valor no vetor $$tin[f]$$. Quando sair de uma DFS, guardaremos o $$timer$$ no vetor $$tout[f]$$. Nessa linearização, uma vértice $$x$$ está na sub-árvore de $$y$$ se $$tin[y] \leq tin[x] \leq tout[y]$$. Podemos usar essa propriedade, para usarmos uma BIT de marcação, com esse vetor. Sempre que adicionarmos um LCA no conjunto, podemos fazer um update de valor $$1$$ na posição $$tin[LCA]$$ na BIT, e -1 na posição $$tout[LCA] + 1$$. Para verificarmos se um caminho $$i$$ ja foi marcado, basta checar com uma query se a posição $$tin[a_i]$$ ou $$tin[b_i]$$ é maior que ou igual à 1.
Segue o código, comentado, para melhor compreensão:
https://gist.github.com/PedroRacchetti/2d096d20bce98e32ab287becc19791d7