Рассмотрим вершину. Посчитаем количество инверсий, которое получится в результате между парами вершин, лежащими в поддеревьях различных сыновей этой вершины. Заметим, что оно не зависит от порядка вершин в поддеревьях детей, а зависит только от порядка обхода детей в текущей вершине. Найдем для каждой пары детей количество инверсий, если один из них идет раньше другого. И затем за 2p·p, где p — количество детей, динамическим программированием по подмножествам найдем оптимальный порядок обхода. Осталось научиться вычислять количество инверсий, которое образуется между парами детей. Для этого функция обхода дерева будет возвращать сбалансированное дерево поиска, содержащее индексы всех вершин в поддереве. А внутри сливать деревья поиска от детей, каждый раз приливая меньшее к большему, и в конце добавлять туда свой индекс. Тогда, чтобы вычислить количество инверсий между парами детей, переберем все пары детей, для каждой пары переберем все вершины ребенка, размер которого меньше, и для каждой вершины сделаем запросы к дереву поиска второго ребенка, чтобы узнать, сколько там вершин с индексом больше/меньше, чем эта. Оценим асимптотику. Посмотрим на случай, когда мы делаем запрос к дереву поиска с фиксированным индексом. Это значит, что после поднятия в родителя той вершины, в которой произошел запрос, размер поддерева, в котором лежит этот индекс, увеличится хотя бы в 2 раза. Значит, количество запросов с одним индексом будет не больше log(n)·7, каждый запрос выполняется за O(log(n)), итоговая асимптотика получается O(n·2p·p + n·log2(n)·p), где p — максимальное количество детей.