Значення в кореневому дереві#12968

Значення в кореневому дереві (Editorial)

Будемо рахувати відповідь в процесі обходу дерева в глибину. При вході у вершину потрібно додати її значення до множини, а при виході видалити. Тепер після входу потрібно знайти відповідь. Подивимося як зміниться відповідь, якщо ми перейшли від батька до сина. Нехай ми прийшли до вершини . Відповідь може або не змінитися, або збільшитися, якщо найдовший відрізок буде містити значення a_v.

Для того аби знайти найдовший відрізок зі значенням a_v, і оновити ним відповідь, можна використати сет. У цьому сеті ми можемо зберігати відрізки [l, r], такі що на шляху від кореня до цієї вершини були усі значення від до включно. Тепер при вході у вершину цей сет може змінитись в один із чотирьох способів:

Коли ми будемо виходити з вершини , нам треба скасувати усі зміни які ми робили в цій вершині. Ми можемо запам’ятати які відрізки ми видалили з сету при вході і які додали. При виході видалимо ті що додали і додамо ті що видалили.

Складність O(n \cdot \log n).