Fake Plastic Trees

题意翻译

$t$ 组数据，每组给定一个 $n$ 个结点的树， **根为 $1$** ，给定 $2,3,\ldots ,n$ 的父结点 $p_2,p_3,\ldots ,p_n$ 。再给出每个点权值 $a_i$ 的范围 $[l_i,r_i]$ 。 初始每个点的权值均为 $0$ 。每次操作可以选择从 $1$ 开始的树上路径 $b_1,b_2,\ldots,b_k$ （不一定要在叶子处结束），将 $a_{b_i}$ 加上 $c_i$ ，其中 $\{c_i\}$ 是一个 **非负单调非减** 的 **整数** 数列。 问至少多少次操作，可以令所有点点权均在 $[l_i,r_i]$ 范围内。 $1\le t\le 1000,2\le n\le 2\times 10^5,\sum n\le 2\times 10^5,1\le p_i<i,1\le l_i\le r_i\le 10^9$

题目描述

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?

输入输出格式

输入格式

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 < 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 $ .

输出格式

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

输入输出样例

输入样例 #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

说明

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 $ .

**题目大意**：

给定一个包含n个顶点的有根树，顶点编号从1到n。根节点是顶点1，顶点v的父节点是p_v。

每个顶点上写有一个数，初始所有数都是0。设顶点v上写的数为a_v。

对于每个v，我们希望a_v在l_v和r_v之间（l_v <= a_v <= r_v）。

在一次操作中，我们做以下事情：

- 选择某个顶点v。设b_1, b_2, ..., b_k是从顶点1到顶点v的路径上的顶点（意味着b_1 = 1, b_k = v，b_i = p_{b_{i+1}}）。
- 选择一个长度为k的非递减数组c，由非负整数组成：0 <= c_1 <= c_2 <= ... <= c_k。
- 对于每个i（1 <= i <= k），将a_{b_i}增加c_i。

问至少需要多少次操作才能达到我们的目标？

**输入输出格式**：

**输入格式**：

第一行包含一个整数t（1≤t≤1000）——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）——树中顶点的数量。

每个测试用例的第二行包含n-1个整数，p_2, p_3, ..., p_n（1 <= p_i < i），其中p_i表示顶点i的父节点。

接下来的n行中的第i行包含两个整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ 10^9）。

保证所有测试用例的n之和不超过2×10^5。

**输出格式**：

对于每个测试用例输出达到目标所需的最小操作次数。**题目大意**： 给定一个包含n个顶点的有根树，顶点编号从1到n。根节点是顶点1，顶点v的父节点是p_v。 每个顶点上写有一个数，初始所有数都是0。设顶点v上写的数为a_v。 对于每个v，我们希望a_v在l_v和r_v之间（l_v <= a_v <= r_v）。 在一次操作中，我们做以下事情： - 选择某个顶点v。设b_1, b_2, ..., b_k是从顶点1到顶点v的路径上的顶点（意味着b_1 = 1, b_k = v，b_i = p_{b_{i+1}}）。 - 选择一个长度为k的非递减数组c，由非负整数组成：0 <= c_1 <= c_2 <= ... <= c_k。 - 对于每个i（1 <= i <= k），将a_{b_i}增加c_i。 问至少需要多少次操作才能达到我们的目标？ **输入输出格式**： **输入格式**： 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）——树中顶点的数量。 每个测试用例的第二行包含n-1个整数，p_2, p_3, ..., p_n（1 <= p_i < i），其中p_i表示顶点i的父节点。 接下来的n行中的第i行包含两个整数l_i和r_i（1 ≤ l_i ≤ r_i ≤ 10^9）。 保证所有测试用例的n之和不超过2×10^5。 **输出格式**： 对于每个测试用例输出达到目标所需的最小操作次数。