F. Древесные запросы
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево, состоящее из $$$n$$$ вершин. Напомним, что дерево — это неориентированный ацикличный граф. Корнем данного дерева является вершина $$$1$$$.

Требуется обработать $$$q$$$ запросов. В каждом запросе задается вершина дерева $$$v$$$ и целое число $$$k$$$.

Для обработки запроса можно удалять вершины из дерева в произвольном порядке, кроме корня и вершины $$$v$$$. Когда вершина удаляется, ее дети становятся детьми ее родителя. Требуется обработать запрос так, чтобы максимизировать значение $$$c(v) - m \cdot k$$$ (где $$$c(v)$$$ — это итоговое количество детей вершины $$$v$$$, а $$$m$$$ — это количество удаленных вершин). Выведите максимальное значение, которое можно получить.

Запросы независимые: изменения, произведенные над деревом при обработке запроса, не затрагивают другие запросы.

Входные данные

В первой строке записано одно число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Затем следует $$$n-1$$$ строка, в $$$i$$$-й из них записаны два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — концы $$$i$$$-го ребра. Данные ребра образуют дерево.

В следующей строке записано одно целое $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Затем следуют $$$q$$$ строк, в $$$j$$$-й из них записаны два целых числа $$$v_j$$$ и $$$k_j$$$ ($$$1 \le v_j \le n$$$; $$$0 \le k_j \le 2 \cdot 10^5$$$) — параметры $$$j$$$-го запроса.

Выходные данные

На каждый запрос выведите одно целое число — максимальное значение $$$c(v) - m \cdot k$$$, которое можно получить.

Пример
Входные данные
8
6 7
3 2
8 3
5 7
7 4
7 1
7 3
6
1 0
1 2
1 3
7 1
5 0
7 200000
Выходные данные
5
2
1
4
0
4
Примечание

Дерево в первом примере показано на следующем изображении:

Ответы на запросы получаются следующим образом:

  1. $$$v=1,k=0$$$: можно удалить вершины $$$7$$$ и $$$3$$$, так, чтобы у вершины $$$1$$$ стало $$$5$$$ детей (вершины $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$ и $$$8$$$), и счет равен $$$5 - 2 \cdot 0 = 5$$$;
  2. $$$v=1,k=2$$$: можно удалить вершину $$$7$$$, так, чтобы у вершины $$$1$$$ стало $$$4$$$ ребенка (вершины $$$3$$$, $$$4$$$, $$$5$$$ и $$$6$$$), и счет равен $$$4 - 1 \cdot 2 = 2$$$.
  3. $$$v=1,k=3$$$: не надо удалять вершины; тогда у вершины $$$1$$$ станет один ребенок (вершина $$$7$$$), и счет равен $$$1 - 0 \cdot 3 = 1$$$;
  4. $$$v=7,k=1$$$: можно удалить вершину $$$3$$$, так, чтобы у вершины $$$7$$$ стало $$$5$$$ детей (вершины $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$ и $$$8$$$), и счет равен $$$5 - 1 \cdot 1 = 4$$$;
  5. $$$v=5,k=0$$$: что бы вы ни делали, у вершины $$$5$$$ не будет детей, поэтому счет равен $$$0$$$;
  6. $$$v=7,k=200000$$$: не надо удалять вершины; тогда у вершины $$$7$$$ станет $$$4$$$ ребенка (вершины $$$3$$$, $$$4$$$, $$$5$$$ и $$$6$$$), и счет равен $$$4 - 0 \cdot 200000 = 4$$$.