Доброго времени суток!!!
Когда-то давно на Codeforces шло обсуждение link-cut tree в котором подняли вопрос о том, что делать в случае если операции делаются на ребрах, а не на вершинах (как в обычном link-cut tree). Если не ошибаюсь Burunduk1 единственным ответил на этот вопрос, сказав что посередине каждого ребра можно добавить фиктивную вершину и ей сопоставлять ребро. Этот хак выручает в случае операций на изменение в точке (т.е. когда за раз изменяется значение только на одном ребре). Но это никак не спасает в случае если нужно делать изменение на пути ребер (Heavy-light decomposition без проблем с этим справляется). Кому-нибудь известен способ сделать это, не сильно меняя саму (не меняя совсем) структуру link-cut tree?
А в чём проблема использовать фиктивные вершины для групповых операций? Если вырезать путь, который нам нужен, то можно будет применить к нему групповую операцию для рёбер. Если вершины тоже надо модифицировать, то можно просто в декартовом дереве хранить два типа модификаций — вершинные и рёберные. Не вижу тут сложности.
Видимо стоило написать предполагается использование splay деревьев в link-cut (потому что его обычно и используют). С декартовым так можно но там нужно сильно поменять структуру поскольку операции нужно делать только по нечетным в 0-индексации. То же можно ухищриться сделать и со splay, но это сильно меняет общую структуру
Нам на самом деле надо не "нечётные в 0-индексации", а "реберные" или "вершинные". Эти свойства у элементов фиксированные, поэтому никаких сильных изменений структуры нет, мне кажется. Каждая вершина splay-дерева знает про себя, "рёберная" она или нет, а также сколько у неё в поддереве "рёберных", и применяет операции соответственно.
Да точно, простое решение которое я и искал. Вопрос закрыт: нужно просто поддерживать тип вершины и количество реберных в поддереве.