CF1693B.Fake Plastic Trees

We are given a rooted tree consisting of $n$ vertices numbered from $1$ to $n$. The root of the tree is the vertex $1$ and the parent of the vertex $v$ is $p_v$.

There is a number written on each vertex, initially all numbers are equal to $0$. Let's denote the number written on the vertex $v$ as $a_v$.

For each $v$, we want $a_v$ to be between $l_v$ and $r_v$ $(l_v \leq a_v \leq r_v)$.

In a single operation we do the following:

• Choose some vertex $v$. Let $b_1, b_2, \ldots, b_k$ be vertices on the path from the vertex $1$ to vertex $v$ (meaning $b_1 = 1$, $b_k = v$ and $b_i = p_{b_{i + 1}}$).
• Choose a non-decreasing array $c$ of length $k$ of nonnegative integers: $0 \leq c_1 \leq c_2 \leq \ldots \leq c_k$.
• For each $i$ $(1 \leq i \leq k)$, increase $a_{b_i}$ by $c_i$.

What's the minimum number of operations needed to achieve our goal?

我们给出一棵有 $n$ 个顶点的有根树，顶点编号为 $1$ 到 $n$。树的根为顶点 $1$，顶点 $v$ 的父节点为 $p_v$。

每个顶点上写有一个数字，初始时所有数字均为 $0$。记顶点 $v$ 上写的数字为 $a_v$。

对每个顶点 $v$，我们希望 $a_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$，且对每个 $i$ 有 $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$。

达成目标所需的最少操作次数是多少？

The first line contains an integer $t$ $(1\le t\le 1000)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(2\le n\le 2 \cdot 10^5)$ — the number of the vertices in the tree.

The second line of each test case contains $n - 1$ integers, $p_2, p_3, \ldots, p_n$ $(1 \leq p_i \lt i)$, where $p_i$ denotes the parent of the vertex $i$.

The $i$-th of the following $n$ lines contains two integers $l_i$ and $r_i$ $(1 \le l_i \le r_i \le 10^9)$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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 \lt 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$。

For each test case output the minimum number of operations needed.

对于每个测试用例，输出所需的最少操作次数。

In the first test case, we can achieve the goal with a single operation: choose $v = 2$ and $c = [1, 2]$, resulting in $a_1 = 1, a_2 = 2$.

In the second test case, we can achieve the goal with two operations: first, choose $v = 2$ and $c = [3, 3]$, resulting in $a_1 = 3, a_2 = 3, a_3 = 0$. Then, choose $v = 3, c = [2, 7]$, resulting in $a_1 = 5, a_2 = 3, a_3 = 7$.

在第一个测试用例中，我们可以通过一次操作达成目标：选择 $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$。