CF1693B Fake Plastic Trees

给定一棵有根树，共有 $n$ 个顶点，编号为 $1$ 到 $n$。树的根为顶点 $1$，顶点 $v$ 的父节点为 $p_v$。 每个顶点上写有一个数字，初始时所有顶点上的数字均为 $0$。我们用 $a_v$ 表示顶点 $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$，且 $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$。 请问最少需要多少次操作才能使所有顶点的 $a_v$ 均满足要求？

第一行包含一个整数 $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$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^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$。 由 ChatGPT 4.1 翻译