Root дерево произвольно и предварительно вычислить расстояние от root до каждого узла. Затем для каждого запроса (a,b) вычисляется наименьший общий предок из a и b (назовите его c), и тогда расстояние между ними будет (с dist[i], представляющим расстояние от root) dist[a]+dist[b]-2*dist[c]. Предварительное вычисление расстояния выполняется в O(N), предварительное вычисление LCA - в O(NlogN), и каждый отдельный запрос может выполняться в O(logN) (в зависимости от реализации).
В сети много ресурсов по этой проблеме, поэтому не стесняйтесь Google еще немного, если страница Hackerrank, на которую я ссылался, недостаточна.