Будемо рахувати відповідь в процесі обходу дерева в глибину. При вході у вершину потрібно додати її значення до множини, а при виході видалити. Тепер після входу потрібно знайти відповідь. Подивимося як зміниться відповідь, якщо ми перейшли від батька до сина. Нехай ми прийшли до вершини . Відповідь може або не змінитися, або збільшитися, якщо найдовший відрізок буде містити значення a_v.
Для того аби знайти найдовший відрізок зі значенням a_v, і оновити ним відповідь, можна використати сет. У цьому сеті ми можемо зберігати відрізки [l, r], такі що на шляху від кореня до цієї вершини були усі значення від до включно. Тепер при вході у вершину цей сет може змінитись в один із чотирьох способів:
Ніяк не зміниться, якщо число a_v уже зустрічалось на шляху до кореня.
Утвориться новий відрізок довжини 1 — [a_v, a_v].
Довжина якогось відрізка збільшиться на 1. Такий відрізок мав мати або r = a_v - 1, або l = a_v + 1.
Два відрізки об’єднаються в один, відрізки [l, a_v - 1] та [a_v + 1, r] об’єднаються в один [l, r].
Коли ми будемо виходити з вершини , нам треба скасувати усі зміни які ми робили в цій вершині. Ми можемо запам’ятати які відрізки ми видалили з сету при вході і які додали. При виході видалимо ті що додали і додамо ті що видалили.
Складність O(n \cdot \log n).