Наткнулся на лекцию, где был приведена данная техника, но анализа асимптотики не было, но было сказано, что она составляет O(n*logn), где n — количество вершин в дереве.

Какая идея решения этой задачи ( https://old.informatics.msk.ru/mod/statements/view3.php?chapterid=112916# )? Пытался что-то придумать с хранением отсортированных циклических сдвигов (в итоге можно сравнивать только первые сдвиги для префикса и суффикса) и каждый раз, добавляя новый элемент к префиксу и суффиксу, пересортировывать эти сдвиги, но не знаю, возможно ли это сделать оптимально по времени.