Несколько раз пытался решить задачу, но так и не придумал подходящего решения, буду благодарен за помощь(подсказку).

Задача 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.