AlexanderBolshakov's blog

By AlexanderBolshakov, 11 years ago, In Russian

Рассмотрим такую абстрактную задачу: дано корневое дерево, и у нас есть три вида запросов:

  1. Удалить какое-либо поддерево
  2. Добавить в дерево одиночную вершину, подвесив ее за произвольного предка
  3. Для двух вершин А и В сказать: является ли А предком В? (В оригинале нужно было искать LCA двух вершин)

Я слышал, что эта задача имеет простое и красивое решение (без дерамид и прочей мерзости). Может ли кто-нибудь им поделиться?