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

[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$n$ vertices numbered from 1$1$ to n$n$. The root of the tree is the vertex 1$1$ and the parent of the vertex v$v$ is pv$p_v$.

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

For each v$v$, we want av$a_v$ to be between lv$l_v$ and rv$r_v$ (lv≤av≤rv)$(l_v\le a_v\le r_v)$.

In a single operation we do the following:

• Choose some vertex v$v$. Let b1,b2,…,bk$b_1,b_2,\dots ,b_k$ be vertices on the path from the vertex 1$1$ to vertex v$v$ (meaning b1=1$b_1=1$, bk=v$b_k=v$ and bi=pbi+1$b_i=p_{b_{i+1}}$).
• Choose a non-decreasing array c$c$ of length k$k$ of nonnegative integers: 0≤c1≤c2≤…≤ck$0\le c_1\le c_2\le \dots \le c_k$.
• For each i$i$ (1≤i≤k)$(1\le i\le k)$, increase abi$a_{b_i}$ by ci$c_i$.

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

Solution Click Below:-  CLICK HERE

Input

The first line contains an integer t$t$ (1≤t≤1000)$(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$n$ (2≤n≤2⋅105)$(2\le n\le 2\cdot {10}^5)$  — the number of the vertices in the tree.

Creep Codeforces Solution

Paranoid String Codeforces Solution

Directional Increase Codeforces Solution

Fake Plastic Trees Codeforces Solution

Keshi in Search of AmShZ Codeforces Solution

Decinc Dividing Codeforces Solution

The second line of each test case contains n−1$n-1$ integers, p2,p3,…,pn$p_2,p_3,\dots ,p_n$ (1≤pi<i)$(1\le p_i<i)$, where pi$p_i$ denotes the parent of the vertex i$i$.

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

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

Output

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