Это максимизационная версия задачи. Разница между версиями заключается в том, что в этой версии вам нужно найти максимальную возможную глубину среди всех общих деревьев. Также ограничение на $$$n$$$ в этой версии выше. Вы можете делать взломы, только если все версии задачи решены.

На Рождество Тортинита и Ариетта получили по рождественской ёлке. По случайному совпадению, их деревья имеют одинаковые свойства: оба имеют $$$n+1$$$ вершину и корень в вершине $$$0$$$. В своей рождественской открытке к вам каждая из них прилагает последовательность обхода DFS своего дерева после своих приветствий. Напомним, что последовательность обхода DFS генерируется следующим псевдокодом.

dfs_order = []

def dfs(v):
    dfs_order.append(v)
    выбрать любую перестановку s детей вершины v
    for child in s:
        dfs(child)

dfs(корень)

Пусть последовательность обхода DFS дерева Тортиниты будет $$$a_0, a_1, \ldots, a_n$$$, а дерева Ариетты — $$$b_0, b_1, \ldots, b_n$$$. Вы замечаете, что $$$a_0 = b_0 = 0$$$, и поскольку они сёстры-близнецы, вы задаетесь вопросом, могли ли они получить одно и то же дерево. Вы также чувствуете, что для своей рождественской ёлки сёстры не выберут тривиальную структуру. Поэтому вы хотите найти максимальную возможную глубину$$$^{\text{∗}}$$$ среди всех общих деревьев для обеих последовательностей.