Несколько раз пытался решить задачу, но так и не придумал подходящего решения, буду благодарен за помощь(подсказку).
Задача E.Корпорация с KPI-Open 2014.
Есть дерево из N вершин(1..n), каждой вершине соответствует число ai. Поступает m запросов вида (s, t), каждый запрос означает что поддерево в вершине s подвесили к вершине t(гарантируется что t не принадлежит поддереву s). Для каждого запроса вывести 2 числа: сумму значений записанных в четных вершинах и сумму значений записанных в нечетных вершинах(четность вершины считается от корня, то есть корень четный, сыновья корня — нечетные и т.д.). (N,M<=10^5; ai<=1000)
Ссылка на полное условие: http://kpi-open.org/static/uploads/tasks-2014/kpi-open2014-tour-1-ru.pdf.
Наверное так (но я не уверен). Выписываем обход дерева в массив. (обычный dfs). Но на самом деле не совсем обычный. В нашем массиве будут пропуски под незначащие элементы. Более формально: Добавим фиктивные вершины, так чтобы при обходе нашего дерева все четные вершины стояли на четных местах, а нечетные на нечетных.(так по-моему всегда можно сделать). Далее тупо.
Надо уметь извлекать отрезок массива, и вставлять в другие место(это наша операция).
Также надо узнавать сумму на четных местах и сумму на нечетных.
Это стандартная задача. Или не совсем стандартная. Но в любом случее строим декартячку, одно по четным позициям, другое по нечетным. И там уже вроде все можно.
Как-то так.
Спасибо, но я не понял как именно формируется массив, и как мы узнаем границы отрезка который нужно вырезать. Можно поподробнее, если не сложно. Как я понял , если мы имеем корень 0, а у него 2 сына 1, 2, а у 2 сын 3, тогда массив будет выглядеть вот так [0,1,пропуск,2,3].
Да вы правильно построили массив. Вы поняли порядок добавления. Когда ставим вершину надо смотреть нужно сделать перед ней пропуск или нет.(по четности).
Изначально границы массива мы можем легко определить.
Как поддерживать границы. Это проблема, вы правы. Но мне кажется это можно сделать. Надо присваисать на пути от вершины к корню значение или что-то в этом духе. Я не умею это делать. Пусть более опытные участники подскажут.
в любом случае хард какой-то.....
Кто-нибудь может подсказать решение?
Думаю, это может помочь.