Два дерева#401

Два дерева (Розбір)

Підзадачі мають однаковий розв'язок, оскільки всі вони мають досить низькі обмеження. Розглянемо запити наступним чином:

  1. змінити стан вершини за ;

  2. викликати bfs на поточній версії графа.

Ми будемо виконувати BFS на цих двох деревах з додатковими ребрами між увімкненими листками. Це призведе до часової складності , де — кількість запитів другого типу.