给你一棵由 $$$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$$$ 的最大值。
示例
输入 #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
输出 #1
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$$$。