Всем привет. Нужна помощь в решении задачи: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=66&page=show_problem&problem=3145 Среди тех методов, которые напрашиваются: heavy-light декомпозиция с использованием неявных декартовых деревьев (чтобы можно было выполнять запросы первого типа — переподвешивание, с соответствующим перестроением декомпозиции (тяжелость-легкость ребер может измениться только на пути от переподвешиваемой вершины до корня её дерева), неявные декартовы деревья как раз нужны для отрезания и приклеивания отрезков друг к другу в вершинах до корня). Но грубая оценка для сложности такого переподвешивания O(n*log(n)). Any ideas? Спасибо.