Недавно узнал про такую интересную структуру данных как Heavy-Light декомпозицию(Статья в вики). Решил задачу на тимусе, но хотелось что-то посложнее... Поэтому специально зарегистрировался на SPOJ.com нашел задачу QTREE3 закодил и отправил. Но вот в чем проблема: она не проходит ни одни тесты. Решил погуглить но ничего дельного не нашел. Я прошу подправить мою идею если она оказалась не совсем правильной.

Вот в чем она состоит:

1. Сделать HLD
2. Обновлять цвета вершин с помощью дерева отрезков
3. На каждом пути который мне встречается брать самую последнюю черную вершину

UPD: Все я наконец понял свою ошибку. Почему то если я делаю дерево отрезков для каждого пути то оно проходит) Окончательный код.