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

题意翻译

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