Изменения

Будем рассматривать каждую вершину дерева, предполагая, что она может являться корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве снова при помощи функции, [[Обход в глубину, цвета вершин|обхода обходящей дерево в глубину]]. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, как мы обошли всё дерево и нашли корень дерева поиска с наибольшим количеством вершин, запускаем процедуру, выводящую все вершины на экран.

В переменную <tex>\mathtt{maxdp}</tex>, изначально равную <tex>\mathrmmathtt{-1}</tex>, запишем число вершин максимального поддерева поиска. Будем также вместе с <tex>\mathtt{maxdp}</tex> обновлять <tex>\mathtt{maxroot}</tex>, где будет храниться корень такого поддерева. Чтобы найти <tex>\mathtt{maxdp}</tex>, обойдём вершины и для каждой из них с помощью процедуры <tex>\mathtt{dfs}</tex>, на вход которой подаются сама вершина, максимально и минимально возможные элементы поддерева и количество вершин, посчитаем число элементов, принадлежащих максимальному дереву поиска, для которого данная вершина является корнем. Если результат после обхода вершины оказался больше значения в переменной <tex>\mathtt{maxdp}</tex>, обновляем <tex>\mathtt{maxdp}</tex> и <tex>\mathtt{maxroot}</tex>. Затем переходим к следующей вершине. После того как мы прошлись по всему дереву, посчитали <tex>\mathtt{maxdp}</tex> и нашли <tex>\mathtt{maxroot}</tex>, запускаем процедуру <tex>dfsPrint(maxroot, -INF, INF)</tex> для вывода вершин поддерева поиска. До запуска процедуры <tex>dfs</tex> от каждой вершины переменная <tex>dp</tex> равна единице.