Link-cut tree: Групповые операции на ребрах

Правка ru1, от Edvard, 2015-07-19 17:35:53

Доброго времени суток!!!

Когда-то давно на Codeforces шло обсуждение link-cut tree в котором подняли вопрос о том, что делать в случае если операции делаются на ребрах, а не на вершинах (как в обычном link-cut tree). Если не ошибаюсь Burunduk1 единственным ответил на этот вопрос, сказав что посередине каждого ребра можно добавить фиктивную вершину и ей сопоставлять ребро. Этот хак выручает в случае операций на изменение в точке (т.е. когда за раз изменяется значение только на одном ребре). Но это никак не спасает в случае если нужно делать изменение на пути ребер (Heavy-light decomposition без проблем с этим справляется). Кому-нибудь известен способ сделать это, не сильно меняя саму (не меняя совсем) структуру link-cut tree?

Теги link-cut, tree, групповые операции, групповая модификация, hld, heavy-light

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Edvard 2015-07-19 17:35:53 798 Первая редакция (опубликовано)