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?


-----Input-----

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


-----Output-----

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


-----Examples-----

Input
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
Output
1
2
2
5


-----Note-----

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

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys
I = sys.stdin.readline
R = lambda : map(int, I().split())
for _ in [0] * int(I()):
	n = int(I()) + 1
	p = [0, 0] + [*R()]
	(l, r, mx, z) = ([0] * n, [0] * n, [0] * n, 0)
	for i in range(1, n):
		(l[i], r[i]) = R()
	for i in range(n - 1, 0, -1):
		if mx[i] < l[i]:
			mx[i] = r[i]
			z += 1
		mx[p[i]] += min(mx[i], r[i])
	print(z)


t = int(input())
for _ in range(t):
	n = int(input()) + 1
	P = [0, 0] + list(map(int, input().split()))
	L = [0] * (n + 1)
	R = [0] * (n + 1)
	Val = [0] * (n + 1)
	ans = 0
	for i in range(1, n):
		(L[i], R[i]) = map(int, input().split())
	for i in range(n - 1, 0, -1):
		if Val[i] < L[i]:
			Val[i] = R[i]
			ans += 1
		Val[P[i]] += min(Val[i], R[i])
	print(ans)


import sys

def solve():
	n = int(input())
	p = [0] + list(map(int, input().split()))
	mm = [0] * n
	lr = []
	ans = 0
	for i in range(n):
		lr.append(list(map(int, input().split())))
	for i in range(n - 1, -1, -1):
		if mm[i] < lr[i][0]:
			mm[i] = lr[i][1]
			ans += 1
		if p[i] != 0:
			mm[p[i] - 1] += min(mm[i], lr[i][1])
	print(ans)
for _ in range(int(input())):
	solve()


def solve_testcase(n, parents, vals):
	num_children = [0] * n
	for x in parents:
		num_children[x - 1] += 1
	leaves = [i for (i, x) in enumerate(num_children) if x == 0]
	max_sums = [0 for _ in range(n)]
	ans = 0
	while leaves:
		leaf = leaves.pop()
		high = max_sums[leaf]
		(want_low, want_high) = vals[leaf]
		if leaf == 0:
			if want_low <= high:
				return ans
			return ans + 1
		my_par = parents[leaf - 1] - 1
		num_children[my_par] -= 1
		if num_children[my_par] == 0:
			leaves.append(my_par)
		if want_low > high:
			ans += 1
			high = want_high
		high = min(high, want_high)
		max_sums[my_par] += high
	return ans
to_print = []
test_count = int(input())
for _ in range(test_count):
	length = int(input())
	my_pars = list(map(int, input().split()))
	vals = [tuple(map(int, input().split())) for _ in range(length)]
	to_print.append(solve_testcase(length, my_pars, vals))
print(*to_print, sep='\n')


import sys
sys.setrecursionlimit(2 * 10 ** 6)

def test():
	pass

def main():
	N = int(input())
	for _ in range(N):
		n = int(input())
		par = list(map(int, input().split()))
		lrs = []
		for _ in range(n):
			(l, r) = map(int, input().split())
			lrs.append((l, r))
		chs = [[] for _ in range(n)]
		for (i, p) in enumerate(par):
			chs[p - 1].append(i + 1)

		def dfs(i):
			if chs[i]:
				ans = 0
				ms = 0
				for j in chs[i]:
					(c, m) = dfs(j)
					ms += m
					ans += c
				if ms < lrs[i][0]:
					ans += 1
					ms = lrs[i][1]
				ms = min(ms, lrs[i][1])
				return (ans, ms)
			else:
				return (1, lrs[i][1])
		print(dfs(0)[0])

def init():
	import sys
	import os
	if 'CP_LOCAL_ENV' in os.environ:
		test()
		sys.stdin = open('test.txt')
init()
main()


M = 200000
G = [[] for _ in range(M)]
L = [0] * M
R = [0] * M

def dfs(cur):
	cnt = 0
	m_sum = 0
	l = L[cur]
	r = R[cur]
	for nxt in G[cur]:
		(c, m) = dfs(nxt)
		cnt += c
		m_sum += m
	if m_sum < l:
		return (cnt + 1, r)
	else:
		return (cnt, min(r, m_sum))

def solve():
	N = int(input())
	for (c, p) in enumerate([int(i) for i in input().split()], 1):
		p -= 1
		G[p].append(c)
	for i in range(N):
		(l, r) = [int(j) for j in input().split()]
		L[i] = l
		R[i] = r
	(res, m) = dfs(0)
	for i in range(N):
		G[i] = []
		L[i] = R[i] = 0
	return str(res)
T = int(input())
ans = [solve() for _ in range(T)]
print('\n'.join(ans))


T = int(input())
for i in range(0, T):
	n = int(input())
	p = list(map(int, input().split()))
	e = [[] for i in range(0, n)]
	l = [0 for i in range(0, n)]
	r = [0 for i in range(0, n)]
	for i in range(1, n):
		e[p[i - 1] - 1].append(i)
	for i in range(0, n):
		(l[i], r[i]) = map(int, input().split())
	ans = 0
	mx = [0 for i in range(0, n)]
	for x in range(n - 1, -1, -1):
		for y in e[x]:
			mx[x] += mx[y]
		if mx[x] >= l[x]:
			mx[x] = min(mx[x], r[x])
		else:
			ans += 1
			mx[x] = r[x]
	print(ans)


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	for _ in range(int(input())):
		n = int(input())
		parent = list(map(int, input().split()))
		graph = [[] for _ in range(n)]
		for (i, el) in enumerate(parent):
			graph[el - 1].append(i + 1)
		arr = []
		for _ in range(n):
			arr.append(list(map(int, input().split())))
		ans = [0]

		def solve(node, par):
			if graph[node] == 0:
				ans[0] += 1
				return arr[node][1]
			p = arr[node][0]
			f = False
			temp = 0
			for nie in graph[node]:
				if nie != par:
					v = solve(nie, node)
					temp += v
			if temp >= p:
				f = True
				return min(arr[node][1], temp)
			if not f:
				ans[0] += 1
			return arr[node][1]
		solve(0, -1)
		print(ans[0])
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = [0 for i in range(n)]
	r = [0 for i in range(n)]
	for i in range(n):
		(l[i], r[i]) = map(int, input().split())
	child = [[] for i in range(n)]
	for i in range(n - 1):
		child[arr[i] - 1].append(i + 1)
	ans = 0
	val = [0 for i in range(n)]
	for x in range(n - 1, -1, -1):
		for y in child[x]:
			val[x] += val[y]
		if val[x] >= l[x]:
			val[x] = min(val[x], r[x])
		else:
			ans += 1
			val[x] = r[x]
	print(ans)


input = __import__('sys').stdin.readline

def solve():
	n = int(input())
	adj = [[] for _ in range(n)]
	parent = [0] * n
	parent = [-1] + list(map(lambda x: int(x) - 1, input().split()))
	adj = [[] for _ in range(n)]
	for u in range(1, n):
		adj[parent[u]].append(u)
	order = []
	stack = [0]
	while len(stack) > 0:
		u = stack.pop()
		order.append(u)
		for v in adj[u]:
			stack.append(v)
	(L, R) = ([-1] * n, [-1] * n)
	for i in range(n):
		(L[i], R[i]) = map(int, input().split())
	ans = 0
	total = [0] * n
	for u in order[::-1]:
		if total[u] < L[u]:
			ans += 1
			total[u] = R[u]
		total[parent[u]] += min(total[u], R[u])
	print(ans)
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split(' ')))
	l = []
	r = []
	for _ in range(n):
		temp = input().split(' ')
		l.append(int(temp[0]))
		r.append(int(temp[1]))
	children = [[] for _ in range(n)]
	for i in range(n - 1):
		children[p[i] - 1].append(i + 1)
	needy = [0 for _ in range(n)]

	def parsevert(i: int):
		total = 0
		for i2 in children[i]:
			total += parsevert(i2)
		if total > r[i]:
			total = r[i]
		if total < l[i]:
			needy[i] = 1
			total = r[i]
		return total
	parsevert(0)
	print(sum(needy))


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
INF = 10 ** 10

def dfs(Parent, Children, L, R, p):
	if Children[p]:
		l = 0
		r = 0
		n = 0
		for p1 in Children[p]:
			(r1, n1) = dfs(Parent, Children, L, R, p1)
			r += r1
			n += n1
		r2 = min(r, R[p])
		if L[p] <= r2:
			return (min(r2, R[p]), n)
		else:
			return (R[p], n + 1)
	else:
		return (R[p], 1)

def solve(N, Parent, Children, L, R):
	(r, n) = dfs(Parent, Children, L, R, 0)
	return n
T0 = int(input())
for _ in range(T0):
	N = int(input())
	Parent = [-1] * N
	Children = [list() for _ in range(N)]
	P = list(map(int, input().split()))
	for i in range(N - 1):
		Parent[i + 1] = P[i] - 1
		Children[P[i] - 1].append(i + 1)
	(L, R) = ([], [])
	for _ in range(N):
		(l, r) = map(int, input().split())
		L.append(l)
		R.append(r)
	print(solve(N, Parent, Children, L, R))


from collections import deque
t = int(input())
while t:
	t -= 1
	n = int(input())
	l = [int(x) - 1 for x in input().split()]
	rng = []
	for i in range(n):
		rng.append([int(x) for x in input().split()])
	deg = [0] * n
	for (i, x) in enumerate(l):
		deg[x] += 1
	val = [0] * n
	q = deque()
	ans = 0
	for i in range(n):
		if deg[i] == 0:
			ans += 1
			q.append(i)
			val[i] = rng[i][1]
	while q:
		x = q.pop()
		px = l[x - 1]
		deg[px] -= 1
		val[px] += val[x]
		if deg[px] == 0:
			q.append(px)
			if val[px] < rng[px][0]:
				val[px] = rng[px][1]
				ans += 1
			elif val[px] > rng[px][1]:
				val[px] = rng[px][1]
	print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
if 'pypyjit' in sys.builtin_module_names:
	import pypyjit
	pypyjit.set_param('max_unroll_recursion=-1')
T = int(input())
for t in range(T):
	N = int(input())
	P = list(map(int, input().split()))
	LR = [list(map(int, input().split())) for _ in range(N)]
	child = [[] for _ in range(N)]
	for (i, p) in enumerate(P):
		p -= 1
		child[p].append(i + 1)

	def dfs(pos=0):
		(l0, r0) = LR[pos]
		cnt = 0
		(l, r) = (0, 0)
		for c in child[pos]:
			(l1, r1, cnt1) = dfs(c)
			l += l1
			r += r1
			cnt += cnt1
		if l0 > r:
			cnt += 1
			r = r0
			l = l0
		else:
			r = min(r0, r)
			l = max(l, l0)
		return (l, r, cnt)
	(_, _, ans) = dfs()
	print(ans)


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		dit = {}
		for i in range(n - 1):
			if arr[i] in dit:
				dit[arr[i]].append(i + 2)
			else:
				dit[arr[i]] = [i + 2]
		req = {}
		for i in range(n):
			req[i + 1] = list(map(int, input().split()))
		global ans
		ans = 0

		def fun(p):
			global ans
			if p not in dit:
				ans += 1
				return req[p][1]
			maxx = 0
			for e in dit[p]:
				maxx += fun(e)
			if maxx >= req[p][0]:
				return min(maxx, req[p][1])
			else:
				ans += 1
				return req[p][1]
		fun(1)
		print(ans)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


from os import error
import sys
input = sys.stdin.readline
DEBUG = False

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	n = inp()
	tree = []
	for i in range(n + 1):
		tree.append({'v': (0, 0), 'child': []})
	parents = inlt()
	for (i, p) in enumerate(parents):
		v = i + 1
		p = p - 1
		tree[p]['child'].append(v)
	for i in range(n):
		(l, v) = inlt()
		tree[i]['v'] = (l, v)

	def down(i):
		(l, v) = tree[i]['v']
		if len(tree[i]['child']) == 0:
			if l <= 0 and v >= 0:
				return (None, None)
			else:
				return (1, v)
		required = 0
		collected = 0
		chlds = tree[i]['child']
		for c in chlds:
			(rs, cv) = down(c)
			if cv is not None:
				collected += cv
				required += rs
		if collected < l:
			required += 1
			collected = v
		elif collected > v:
			collected = v
		return (required, collected)
	(rs, _) = down(0)
	return rs
n = inp()
for t in range(n):
	ans = solve()
	print(ans)


import queue
from sys import stdin

class Node:

	def __init__(self):
		self.parent = None
		self.l = 0
		self.r = 0
		self.val = 0
		self.indeg = 0

	def __repr__(self) -> str:
		return f'{self.l} {self.r}'

def merge(curr, res):
	while curr and curr.indeg == 0:
		carry = 0
		if curr.val >= curr.l:
			carry = min(curr.val, curr.r)
		else:
			carry = curr.r
			res[0] += 1
		if curr.parent:
			curr.parent.val += carry
			curr.parent.indeg -= 1
		curr = curr.parent

def solve():
	n = int(stdin.readline())
	nodes = [Node() for i in range(n)]
	leaves = set(range(1, n))
	parents = list(map(int, stdin.readline().split()))
	for i in range(1, n):
		nodes[i].parent = nodes[parents[i - 1] - 1]
		nodes[parents[i - 1] - 1].indeg += 1
		leaves.discard(parents[i - 1] - 1)
	for i in range(n):
		curr = nodes[i]
		(l, r) = map(int, stdin.readline().split())
		curr.l = l
		curr.r = r
	res = [0]
	for leaf in leaves:
		merge(nodes[leaf], res)
	print(res[0])
for _ in range(int(stdin.readline())):
	solve()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000 + 3)

def f(n):
	arr = []
	s1 = s2 = 0
	for i in graph[n]:
		arr.append(i)
		line = f(i)
		(a, b) = (line[0], line[1])
		s1 += a
		s2 += b
	if len(arr) == 0:
		return [1, r[n][1]]
	elif s2 >= r[n][0]:
		return [s1, min(r[n][1], s2)]
	else:
		return [s1 + 1, r[n][1]]
t = int(input())
for _ in range(t):
	n = int(input())
	graph = [[] for i in range(n + 1)]
	road = list(map(int, input().split()))
	for i in range(n - 1):
		graph[road[i]].append(i + 2)
	r = [[0, 0] for i in range(n + 1)]
	for i in range(n):
		(a, b) = map(int, input().split())
		(r[i + 1][0], r[i + 1][1]) = (a, b)
	line = f(1)
	print(line[0])