我们得到一棵有根树,由 $$$n$$$ 顶点组成,编号从 $$$1$$$ 到 $$$n$$$。树的根是顶点 $$$1$$$,顶点 $$$v$$$ 的父节点是 $$$p_v$$$。
每个顶点上都写有一个数字,最初所有数字都等于$$$0$$$。我们将顶点 $$$v$$$ 上写的数字表示为 $$$a_v$$$。
对于每个 $$$v$$$,我们希望 $$$a_v$$$ 介于 $$$l_v$$$ 和 $$$r_v$$$ $$$(l_v \leq a_v \leq r_v)$$$ 之间。
在单个操作中,我们执行以下操作:
- 选择一些顶点$$$v$$$。令 $$$b_1, b_2, \ldots, b_k$$$ 为从顶点 $$$1$$$ 到顶点 $$$v$$$ 的路径上的顶点(即 $$$b_1 = 1$$$、$$$b_k = v$$$ 和 $$$b_i = p_{b_{i + 1}}$$$)。
- 选择长度为 $$$k$$$ 的非减数组 $$$c$$$ 非负整数:$$$0 \leq c_1 \leq c_2 \leq \ldots \leq c_k$$$。
- 对于每个 $$$i$$$ $$$(1 \leq i \leq k)$$$,将 $$$a_{b_i}$$$ 增加 $$$c_i$$$。
实现我们的目标所需的最少操作次数是多少?
输入
第一行包含一个整数 $$$t$$$ $$$(1\le t\le 1000)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2\le n\le 2 \cdot 10^5)$$$ — 树中顶点的数量。
每个测试用例的第二行包含 $$$n - 1$$$ 整数,$$$p_2, p_3, \ldots, p_n$$$ $$$(1 \leq p_i < i)$$$,其中 $$$p_i$$$ 表示顶点 $$$i$$$ 的父顶点。
以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ $$$(1 \le l_i \le r_i \le 10^9)$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出所需的最小操作数。
示例
输入 #1
4 2 1 1 5 2 9 3 1 1 4 5 2 4 6 10 4 1 2 1 6 9 5 6 4 5 2 4 5 1 2 3 4 5 5 4 4 3 3 2 2 1 1
输出 #1
1 2 2 5
注意
在第一个测试用例中,我们可以通过单个操作来实现目标:选择 $$$v = 2$$$ 和 $$$c = [1, 2]$$$,从而得到 $$$a_1 = 1, a_2 = 2$$$。
在第二个测试用例中,我们可以通过两个操作来实现目标:首先,选择 $$$v = 2$$$ 和 $$$c = [3, 3]$$$,得到 $$$a_1 = 3, a_2 = 3, a_3 = 0$$$。然后,选择 $$$v = 3, c = [2, 7]$$$,得到 $$$a_1 = 5, a_2 = 3, a_3 = 7$$$。