## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Fake Plastic Trees Codeforces Solution | Codeforces Problem Solution 2022

D. Fake Plastic Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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}$ $\left({l}_{v}\le {a}_{v}\le {r}_{v}\right)$.

In a single operation we do the following:

• Choose some vertex $v$. Let ${b}_{1},{b}_{2},\dots ,{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\le {c}_{1}\le {c}_{2}\le \dots \le {c}_{k}$.
• For each $i$ $\left(1\le i\le k\right)$, increase ${a}_{{b}_{i}}$ by ${c}_{i}$.

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

Input

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

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

The second line of each test case contains $n-1$ integers, ${p}_{2},{p}_{3},\dots ,{p}_{n}$ $\left(1\le {p}_{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}$ $\left(1\le {l}_{i}\le {r}_{i}\le {10}^{9}\right)$.

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

Output

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