Задача с контеста Яндекс
Даются число n - количество массивов.
После n раз дают число k и сам массив. Где число k - длина i - того массива.
Для пары массивов i, j - красотой будем говорить максимальную длину общего префикса. Найти сумму красоты по всем парам i, j.
Например:
3
2
1 2
2
1 3
3
1 2 3
Ответ 4.
Так например для массива 1 2 и 1 3 красота 1. Для 1 2 и 1 2 3 красота 2, для 1 3 и 1 2 3 красота 1.
Ответ 1 + 2 + 1 = 4.

Решение:
Чтобы оптимально решить задачу воспользуемся алгоритмом бор.
Построим дерево. Когда будем добавлять массив в бор сделаем +1 ко всем вершинам бора, таким образом мы узнаем сколько массивов проходило через данную вершину.

Теперь подумаем, как находить ответ одного массива. Пусть мы на вершине v и пытаемся пойти в u.
Пусть v-> count говорит сколько массивов проходило через вершину v.
Когда пытаемся пройти через вершину к u, мы понимаем, что v -> count - u-> count массивов больше с нами не идут дальше по ветке.
Нам нужно знать высоту вершины в дереве, чтобы определить на какую красоту прибавлять. Легко видеть что мы должны прибавить к ответу (v->count - u->count) * h, где h - высота вершины v в дереве.
Не забывайте обработать случай, когда мы в листе.

Таким образом алгоритм получается следующий.
Нам нужна функция, которая умеет добавлять массив в бор, а также умеет считать красоту для одного массива со всеми другими.

Код в комментариях.