K. Подъём за константу

Та же задача, что в F — подняться от города на $k$ дорог к столице, — но запросов десять миллионов, а времени в полтора раза меньше.

Формат тот же, что в задаче F: $n$ и $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^7$), затем $n-1$ родителей, затем $a_1$, $a_2$ и $x$, $y$, $z$. Первое число запроса — город (с поправкой на предыдущий ответ), второе — на сколько дорог готов уехать выпускник.

Выведите сумму номеров городов — ответов на все запросы.