CF1606F.Tree Queries

You are given a tree consisting of $n$ vertices. Recall that a tree is an undirected connected acyclic graph. The given tree is rooted at the vertex $1$.

You have to process $q$ queries. In each query, you are given a vertex of the tree $v$ and an integer $k$.

To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex $v$. When a vertex is deleted, its children become the children of its parent. You have to process a query in such a way that maximizes the value of $c(v) - m \cdot k$ (where $c(v)$ is the resulting number of children of the vertex $v$, and $m$ is the number of vertices you have deleted). Print the maximum possible value you can obtain.

The queries are independent: the changes you make to the tree while processing a query don't affect the tree in other queries.

给你一棵包含 $n$ 个顶点的树。注意：树是一种无向、连通且无环的图。给定的树以顶点 $1$ 为根。

你需要处理 $q$ 个查询。在每个查询中，你将获得树中的一个顶点 $v$ 和一个整数 $k$。

为了处理一个查询，你可以按任意顺序删除树中的任意顶点，但根节点（即顶点 $1$）和顶点 $v$ 不得被删除。当一个顶点被删除时，它的所有子节点将直接成为其父节点的子节点。你需要以某种方式处理该查询，使得表达式 $c(v) - m \cdot k$ 的值最大化（其中 $c(v)$ 表示操作后顶点 $v$ 的子节点数量，$m$ 表示你所删除的顶点总数）。请输出所能得到的最大可能值。

各个查询相互独立：你在处理某个查询时对树所作的修改，不会影响其他查询中树的初始状态。

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

Then $n-1$ lines follow, the $i$-th of them contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$) — the endpoints of the $i$-th edge. These edges form a tree.

The next line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, the $j$-th of them contains two integers $v_j$ and $k_j$ ($1 \le v_j \le n$; $0 \le k_j \le 2 \cdot 10^5$) — the parameters of the $j$-th query.

第一行包含一个整数 $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$ 个查询的参数。

For each query, print one integer — the maximum value of $c(v) - m \cdot k$ you can achieve.

对于每个查询，输出一个整数——你能达到的 $c(v) - m \cdot k$ 的最大值。

The tree in the first example is shown in the following picture:

Answers to the queries are obtained as follows:

1. $v=1,k=0$: you can delete vertices $7$ and $3$, so the vertex $1$ has $5$ children (vertices $2$, $4$, $5$, $6$, and $8$), and the score is $5 - 2 \cdot 0 = 5$;
2. $v=1,k=2$: you can delete the vertex $7$, so the vertex $1$ has $4$ children (vertices $3$, $4$, $5$, and $6$), and the score is $4 - 1 \cdot 2 = 2$.
3. $v=1,k=3$: you shouldn't delete any vertices, so the vertex $1$ has only one child (vertex $7$), and the score is $1 - 0 \cdot 3 = 1$;
4. $v=7,k=1$: you can delete the vertex $3$, so the vertex $7$ has $5$ children (vertices $2$, $4$, $5$, $6$, and $8$), and the score is $5 - 1 \cdot 1 = 4$;
5. $v=5,k=0$: no matter what you do, the vertex $5$ will have no children, so the score is $0$;
6. $v=7,k=200000$: you shouldn't delete any vertices, so the vertex $7$ has $4$ children (vertices $3$, $4$, $5$, and $6$), and the score is $4 - 0 \cdot 200000 = 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$。