Дано дерево, состоящее из \(n\) вершин. Напомним, что дерево — это неориентированный ацикличный граф. Корнем данного дерева является вершина \(1\).
Требуется обработать \(q\) запросов. В каждом запросе задается вершина дерева \(v\) и целое число \(k\).
Для обработки запроса можно удалять вершины из дерева в произвольном порядке, кроме корня и вершины \(v\). Когда вершина удаляется, ее дети становятся детьми ее родителя. Требуется обработать запрос так, чтобы максимизировать значение \(c(v) - m \cdot k\) (где \(c(v)\) — это итоговое количество детей вершины \(v\), а \(m\) — это количество удаленных вершин). Выведите максимальное значение, которое можно получить.
Запросы независимые: изменения, произведенные над деревом при обработке запроса, не затрагивают другие запросы.
Выходные данные
На каждый запрос выведите одно целое число — максимальное значение \(c(v) - m \cdot k\), которое можно получить.
Примечание
Дерево в первом примере показано на следующем изображении:
Ответы на запросы получаются следующим образом:
- \(v=1,k=0\): можно удалить вершины \(7\) и \(3\), так, чтобы у вершины \(1\) стало \(5\) детей (вершины \(2\), \(4\), \(5\), \(6\) и \(8\)), и счет равен \(5 - 2 \cdot 0 = 5\);
- \(v=1,k=2\): можно удалить вершину \(7\), так, чтобы у вершины \(1\) стало \(4\) ребенка (вершины \(3\), \(4\), \(5\) и \(6\)), и счет равен \(4 - 1 \cdot 2 = 2\).
- \(v=1,k=3\): не надо удалять вершины; тогда у вершины \(1\) станет один ребенок (вершина \(7\)), и счет равен \(1 - 0 \cdot 3 = 1\);
- \(v=7,k=1\): можно удалить вершину \(3\), так, чтобы у вершины \(7\) стало \(5\) детей (вершины \(2\), \(4\), \(5\), \(6\) и \(8\)), и счет равен \(5 - 1 \cdot 1 = 4\);
- \(v=5,k=0\): что бы вы ни делали, у вершины \(5\) не будет детей, поэтому счет равен \(0\);
- \(v=7,k=200000\): не надо удалять вершины; тогда у вершины \(7\) станет \(4\) ребенка (вершины \(3\), \(4\), \(5\) и \(6\)), и счет равен \(4 - 0 \cdot 200000 = 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|