Давайте подвесим дерево за какую-нибудь вершин. Теперь вершина пересечения двух путей будет lca для хотя бы одного пути.
ДоказательствоЕсли вершина не является lca для обоих путей, то это означает, что есть два ребра идущих наверх (что невозможно в подвешенном дереве), или они поднимаются по одному ребру, что означает, что у них хотя бы две вершины в пересечении, что также невозможно.
Теперь есть два типа пересечений: с одинаковым lca и разным lca. Давайте посчитаем их по отдельности.
Для каждого пути и его lca найдем поддеревья, в которые этот путь спускается от lca. Получим тройку $$$(lca, subtree1, subtree2)$$$ (если путь не спускается от lca, то заменим на $$$-1$$$), такую что $$$subtree1 < subtree2$$$ или они оба равны $$$-1$$$.
Теперь чтобы посчитать пересечения первого типа мы можем использовать принцип включений-исключений. Запомним все пути, которые имеют одинаковый lca. Теперь нам нужно посчитать число пар путей, таких что у них не совпадает $$$subtree1$$$ и $$$subtree2$$$ (или равен $$$-1$$$). Формула будет $$$cntpath \cdot (cntpath - 1) / 2 - \sum \left(cnt(subtree1, x) + cnt(x, subtree2) - (cnt(subtree1, subtree2) + 1) \right) / 2$$$ (по принципу включений исключений), для всех возможных $$$subtree1$$$ и $$$subtree2$$$, где $$$cntpath$$$ — число путей с данным lca, и $$$cnt(x, y)$$$ — число путей с тройкой $$$(lca, x, y)$$$. Ситуация с $$$-1$$$ примерно такая же, оставляю как упражнение читателю.
Находить пересечения второго типа заметно проще. Нам нужно лишь посчитать число пересечений путей с фиксированным lca и вертикальными путями, которые проходят через это lca (пути необязательно вертикальные, он они содержат и lca и его предка) и после этого вычесть $$$cnt(subtree1)$$$ и $$$cnt(subtree2)$$$, где $$$cnt(x)$$$ — число вертикальных путей, которые спускаются в поддерево $$$x$$$.
После этого мы должны всего-лишь вывести сумму этих чисел. Чтобы посчитать все необходимые функции можно использовать какую-нибудь структуру данных (например переливания) или динамическое программирование по поддеревьям.
Финимальная асимптотика получается $$$O(Mlog^2M)$$$ или $$$O(MlogM)$$$ или даже $$$O(M)$$$, если вы достаточно сильны.