Підзадачі мають однаковий розв'язок, оскільки всі вони мають досить низькі обмеження. Розглянемо запити наступним чином:
змінити стан вершини за ;
викликати bfs на поточній версії графа.
Ми будемо виконувати BFS на цих двох деревах з додатковими ребрами між увімкненими листками. Це призведе до часової складності , де — кількість запитів другого типу.