Рассмотрим строки в порядке от вершины к корню. Тогда количество различных подслов равно количеству различных префиксов таких слов.

Научимся считать количество различных префиксов в наборе слов. Отсортируем все строки. Пусть $$$lcp_i$$$ — количество первых букв, которые совпадают у $$$i$$$-й и $$$i + 1$$$-й строки. Тогда количество различных подстрок равно $$$\sum_{i = 1}^n len_i - \sum_{i = 1}^{n - 1} lcp_i$$$.

Чтобы пересчитывать количество различных строк, будем добавлять строку в нужное место в отсортированный массив и пересчитывать ответ. Пусть новая строка добавилась в позицию $$$i$$$. Тогда количество новых различных подстрок равно $$$len_i - lcp(i, i + 1) - lcp(i - 1, i) + lcp(i - 1, i + 1)$$$.

Чтобы быстро добавлять строку, будем поддерживать упорядоченное множество ($$$set$$$) по лексикографическому порядку слов. Тогда операция вставки будет работать за $$$O(comp \cdot \log{n})$$$, где $$$comp$$$ — время сравнения двух строк, а пересчет за $$$O(lcp)$$$ — время нахождения $$$lcp$$$.

Насчитаем от каждой вершины $$$up_{v, i}$$$ — предка $$$v$$$ на расстоянии $$$2^i$$$, и $$$h_{v, i}$$$ — полиномиальный хеш строки длины $$$2^i$$$, начинающейся в вершине $$$v$$$:

$$$up_{v, i} = up_{up_{v, i - 1}, i - 1}$$$

$$$h_{v, i} = h_{v, i - 1} \cdot p^{2^{i - 1}} + h_{up_{v, i - 1}, i - 1}$$$.

С помощью этого можно сравнивать строки и искать $$$lcp$$$ за $$$\mathcal{O}(\log n)$$$, аналогично двоичным подъемам.

Время работы: $$$\mathcal{O}(n \cdot \log^2(n))$$$.