You are given a rooted tree. It contains $n$ vertices, which are numbered from $1$ to $n$. The root is the vertex $1$.

Each edge has two positive integer values. Thus, two positive integers $a_j$ and $b_j$ are given for each edge.

Output $n-1$ numbers $r_2, r_3, \dots, r_n$, where $r_i$ is defined as follows.

Consider the path from the root (vertex $1$) to $i$ ($2 \le i \le n$). Let the sum of the costs of $a_j$ along this path be $A_i$. Then $r_i$ is equal to the length of the maximum prefix of this path such that the sum of $b_j$ along this prefix does not exceed $A_i$.

Example for $n=9$. The blue color shows the costs of $a_j$, and the red color shows the costs of $b_j$.

Consider an example. In this case:

$r_2=0$, since the path to $2$ has an amount of $a_j$ equal to $5$, only the prefix of this path of length $0$ has a smaller or equal amount of $b_j$;

$r_3=3$, since the path to $3$ has an amount of $a_j$ equal to $5+9+5=19$, the prefix of length $3$ of this path has a sum of $b_j$ equal to $6+10+1=17$ ( the number is $17 \le 19$);

$r_4=1$, since the path to $4$ has an amount of $a_j$ equal to $5+9=14$, the prefix of length $1$ of this path has an amount of $b_j$ equal to $6$ (this is the longest suitable prefix, since the prefix of length $2$ already has an amount of $b_j$ equal to $6+10=16$, which is more than $14$);

$r_5=2$, since the path to $5$ has an amount of $a_j$ equal to $5+9+2=16$, the prefix of length $2$ of this path has a sum of $b_j$ equal to $6+10=16$ (this is the longest suitable prefix, since the prefix of length $3$ already has an amount of $b_j$ equal to $6+10+1=17$, what is more than $16$);

$r_6=1$, since the path up to $6$ has an amount of $a_j$ equal to $2$, the prefix of length $1$ of this path has an amount of $b_j$ equal to $1$;

$r_7=1$, since the path to $7$ has an amount of $a_j$ equal to $5+3=8$, the prefix of length $1$ of this path has an amount of $b_j$ equal to $6$ (this is the longest suitable prefix, since the prefix of length $2$ already has an amount of $b_j$ equal to $6+3=9$, which is more than $8$);

$r_8=2$, since the path up to $8$ has an amount of $a_j$ equal to $2+4=6$, the prefix of length $2$ of this path has an amount of $b_j$ equal to $1+3=4$;

$r_9=3$, since the path to $9$ has an amount of $a_j$ equal to $2+4+1=7$, the prefix of length $3$ of this path has a sum of $b_j$ equal to $1+3+3=7$.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The descriptions of test cases follow.

Each description begins with a line that contains an integer $n$ ($2 \le n \le 2\cdot10^5$) — the number of vertices in the tree.

This is followed by $n-1$ string, each of which contains three numbers $p_j, a_j, b_j$ ($1 \le p_j \le n$; $1 \le a_j,b_j \le 10^9$) — the ancestor of the vertex $j$, the first and second values an edge that leads from $p_j$ to $j$. The value of $j$ runs through all values from $2$ to $n$ inclusive. It is guaranteed that each set of input data has a correct hanged tree with a root at the vertex $1$.

It is guaranteed that the sum of $n$ over all input test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, output $n-1$ integer in one line: $r_2, r_3, \dots, r_n$.


-----Examples-----

Input
4
9
1 5 6
4 5 1
2 9 10
4 2 1
1 2 1
2 3 3
6 4 3
8 1 3
4
1 1 100
2 1 1
3 101 1
4
1 100 1
2 1 1
3 1 101
10
1 1 4
2 3 5
2 5 1
3 4 3
3 1 5
5 3 5
5 2 1
1 3 2
6 2 1
Output
0 3 1 2 1 1 2 3 
0 0 3 
1 2 2 
0 1 2 1 1 2 2 1 1


-----Note-----

The first example is clarified in the statement.

In the second example:

$r_2=0$, since the path to $2$ has an amount of $a_j$ equal to $1$, only the prefix of this path of length $0$ has a smaller or equal amount of $b_j$;

$r_3=0$, since the path to $3$ has an amount of $a_j$ equal to $1+1=2$, the prefix of length $1$ of this path has an amount of $b_j$ equal to $100$ ($100 > 2$);

$r_4=3$, since the path to $4$ has an amount of $a_j$ equal to $1+1+101=103$, the prefix of length $3$ of this path has an amount of $b_j$ equal to $102$, .

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Sorting

Data structures

Graph traversal


Solutions:
from bisect import bisect as br
(R, G) = (lambda : map(int, input().split()), range)
(t,) = R()
for _ in G(t):
	(n,) = R()
	g = [[] for _ in G(n)]
	for i in G(1, n):
		(p, a, b) = R()
		g[p - 1] += [(i, a, b)]
	r = [0] * n
	Pb = [0] * n
	stk = [(0, 0, 0, 0)]
	while stk:
		(u, pa, ub, dep) = stk.pop()
		Pb[dep] = 0 if dep == 0 else Pb[dep - 1] + ub
		r[u] = dep if Pb[dep] <= pa else br(Pb, pa, hi=dep) - 1
		for (v, a, b) in g[u]:
			stk += [(v, pa + a, b, dep + 1)]
	print(*r[1:])


import sys, math
import threading
from bisect import bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def dfs(ans, tre, pb, a, h, v):
	for i in range(len(tre[v][0])):
		a += tre[tre[v][0][i]][1]
		pb[h] = pb[h - 1] + tre[tre[v][0][i]][2]
		h += 1
		ans[tre[v][0][i]] = bisect_right(pb, a, 0, h) - 1
		dfs(ans, tre, pb, a, h, tre[v][0][i])
		a -= tre[tre[v][0][i]][1]
		h -= 1
		pb[h] = 0

def main():
	for _ in range(int(input())):
		n = int(input())
		tre = []
		for i in range(1, n + 1):
			tre.append([[], 0, 0])
		for i in range(1, n):
			(p, a, b) = map(int, input().split())
			tre[p - 1][0].append(i)
			tre[i][1] = a
			tre[i][2] = b
		ans = [0] * n
		a = 0
		h = 1
		pb = [0] * n
		dfs(ans, tre, pb, a, h, 0)
		print(*ans[1:])
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys, bisect, threading
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def dfs(ans, a, b, v, tre, pb):
	for i in range(len(tre[v][0])):
		vtnxt = tre[v][0][i]
		x = tre[vtnxt][1]
		y = tre[vtnxt][2]
		a += x
		b += y
		pb.append(b)
		c = bisect.bisect_right(pb, a)
		ans[vtnxt - 1] = c - 1
		dfs(ans, a, b, vtnxt, tre, pb)
		a -= x
		b -= y
		pb.pop()

def main():
	for _ in range(int(input())):
		n = int(input())
		tre = {}
		for i in range(1, n + 1):
			tre[i] = [[], 0, 0]
		for i in range(2, n + 1):
			(p, a, b) = map(int, input().split())
			tre[p][0].append(i)
			tre[i][1] = a
			tre[i][2] = b
		ans = [0] * n
		a = 0
		b = 0
		pb = [0]
		dfs(ans, a, b, 1, tre, pb)
		print(*ans[1:])
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys, threading
input = sys.stdin.readline
from collections import defaultdict
from bisect import bisect_right as br
sys.setrecursionlimit(10 ** 8)
threading.stack_size(10 ** 8)
sys.setrecursionlimit(10 ** 7)

def solve():
	for test in range(int(input())):
		n = int(input())
		g = defaultdict(list)
		for i in range(2, n + 1):
			(p, a, b) = map(int, input().split())
			g[p].append((i, a, b))
		res = [0] * (n + 1)

		def rec(p, x, y):
			idx = br(y, x)
			res[p] = idx - 1
			for (nn, na, nb) in g[p]:
				y.append(y[-1] + nb)
				rec(nn, x + na, y)
				y.pop()
		rec(1, 0, [0])
		print(*res[2:])
threading.Thread(target=solve).start()


import collections, bisect
import sys, threading
sys.setrecursionlimit(10 ** 8)
threading.stack_size(10 ** 8)
sys.setrecursionlimit(10 ** 7)

def st():
	for _ in range(int(input())):
		n = int(input())
		adj = collections.defaultdict(list)
		a = [0, 0]
		b = [0, 0]
		for i in range(2, n + 1):
			(node, aa, bb) = map(int, input().split())
			adj[node].append(i)
			a.append(aa)
			b.append(bb)
		ans = [0] * (n + 1)

		def solve(root, x, y):
			bb = bisect.bisect_right(y, x)
			ans[root] = bb - 1
			for i in adj[root]:
				y.append(y[-1] + b[i])
				solve(i, x + a[i], y)
				y.pop()
		solve(1, 0, [0])
		print(*ans[2:])
threading.Thread(target=st).start()


from bisect import bisect_right
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	child = defaultdict(list)
	A = [0 for _ in range(n)]
	B = [0 for _ in range(n)]
	for i in range(1, n):
		(p, a, b) = map(int, input().split())
		p -= 1
		child[p].append(i)
		A[i] = a
		B[i] = b
	ANS = [0 for _ in range(n)]
	visited = set()
	Stack = [0]
	(curr_a, curr_b) = (0, 0)
	L = []
	while Stack:
		curr_p = Stack.pop()
		if curr_p in visited:
			curr_a -= A[curr_p]
			curr_b -= B[curr_p]
			L.pop()
		else:
			curr_a += A[curr_p]
			curr_b += B[curr_p]
			L.append(curr_b)
			ANS[curr_p] = bisect_right(L, curr_a) - 1
			Stack.append(curr_p)
			visited.add(curr_p)
			for next_p in child[curr_p]:
				Stack.append(next_p)
	print(*ANS[1:])


import sys, threading
import bisect
lines = list(map(str.strip, sys.stdin.readlines()))
sys.setrecursionlimit(10 ** 9)
threading.stack_size(10 ** 8)

def solve():
	i = 1
	while i < len(lines):
		n = int(lines[i])
		ncopy = n
		i += 1
		children = {}
		node = 2
		while n > 1:
			(parent, a, b) = map(int, lines[i].split(' '))
			if parent not in children:
				children[parent] = []
			children[parent].append([node, a, b])
			node += 1
			i += 1
			n -= 1
		result = {}
		taken = []

		def dfs(node, sum):
			result[node] = bisect.bisect_right(taken, sum)
			if node not in children:
				return
			for (child, left, right) in children[node]:
				taken.append((taken[-1] if len(taken) != 0 else 0) + right)
				dfs(child, sum + left)
				taken.pop()
		dfs(1, 0)
		for j in range(2, ncopy + 1):
			print(result[j], end=' ')
		print()
threading.Thread(target=solve).start()


import sys, threading
sys.setrecursionlimit(400000)
threading.stack_size(10 ** 8)
from bisect import bisect_right
from collections import defaultdict

def rec(curr_p, prev_p, curr_a, L, edge):
	global ANS
	if curr_p != 0:
		idx = bisect_right(L, curr_a)
		ANS[curr_p] = idx - 1
	for (next_p, a, b) in edge[curr_p]:
		if next_p == prev_p:
			continue
		next_a = curr_a + a
		L.append(L[-1] + b)
		rec(next_p, curr_p, next_a, L, edge)
		L.pop()

def main():
	global ANS
	for _ in range(int(input())):
		n = int(input())
		edge = defaultdict(list)
		for i in range(1, n):
			(p, a, b) = map(int, input().split())
			p -= 1
			edge[p].append((i, a, b))
			edge[i].append((p, a, b))
		ANS = [0 for _ in range(n)]
		rec(0, -1, 0, [0], edge)
		print(*ANS[1:])
t = threading.Thread(target=main)
t.start()
t.join()


import bisect
for _ in range(int(input())):
	n = int(input())
	child = {i: [] for i in range(1, n + 1)}
	a = {1: 0}
	b = {1: 0}
	cura = 0
	curb = 0
	cumb = []
	for i in range(2, n + 1):
		(pi, ai, bi) = map(int, input().split())
		child[pi].append(i)
		a[i] = ai
		b[i] = bi
	ans = {1: 0}
	q = [1]
	vis = {}
	while q:
		x = q.pop()
		if x in vis:
			cura -= a[x]
			curb -= b[x]
			cumb.pop()
		else:
			cura += a[x]
			curb += b[x]
			cumb.append(curb)
			ans[x] = bisect.bisect_right(cumb, cura) - 1
			q.append(x)
			vis[x] = True
			for i in child[x]:
				q.append(i)
	for i in range(2, n + 1):
		print(ans[i], end=' ')
	print()


from collections import defaultdict, deque
import bisect
n = int(input().strip())
for i in range(n):
	m = int(input().strip())
	res = ['' for _ in range(m - 1)]
	dic = [[] for _ in range(m + 1)]
	for i in range(2, m + 1):
		a = input().strip().split(' ')
		dic[int(a[0])].append([i, int(a[1]), int(a[2])])
	stack = [[1, 0, 0]]
	B = []
	while stack:
		(p, A, count) = stack[-1]
		if p > 1:
			res[p - 2] = str(bisect.bisect_right(B, A))
		if count < len(dic[p]):
			(pp, a, b) = dic[p][count]
			count += 1
			stack[-1] = [p, A, count]
			stack.append([pp, A + a, 0])
			B.append(B[-1] + b if B else b)
		else:
			stack.pop()
			if B:
				B.pop()
	print(' '.join(res))


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		d = defaultdict(list)
		for i in range(2, n + 1):
			(p, q, r) = sep()
			d[p].append([i, q, r])
		arr = [0]
		ans = [-1] * (n + 1)

		def dfs(curr, res):
			ans[curr] = bisect.bisect_right(arr, res) - 1
			for j in d[curr]:
				arr.append(arr[-1] + j[2])
				dfs(j[0], res + j[1])
				arr.pop()
		dfs(1, 0)
		print(*ans[2:])
sys.setrecursionlimit(2 * 10 ** 5 + 50)
threading.stack_size(10 ** 8)
threading.Thread(target=main).start()


for _ in range(int(input())):
	n = int(input())
	Adjlist = {}
	for i in range(1, n + 1):
		Adjlist[i] = []
	for i in range(2, n + 1):
		(p, a, b) = map(int, input().split())
		Adjlist[p].append((i, a, b))
	stack = [1]
	Prefixsum = {}
	Ans = [0] * (n + 1)
	for i in range(1, n + 1):
		Prefixsum[i] = (0, 0)
	while stack:
		a = stack.pop()
		for p in Adjlist[a]:
			stack.append(p[0])
			(temp1, temp2) = Prefixsum[a]
			Prefixsum[p[0]] = (temp1 + p[1], temp2 + p[2])
	stack = [(1, 0)]
	ListB = [0] * n
	from bisect import bisect
	while stack:
		a = stack.pop()
		for p in Adjlist[a[0]]:
			stack.append((p[0], a[1] + 1))
		t = Prefixsum[a[0]]
		ListB[a[1]] = t[1]
		if t[0] >= t[1]:
			Ans[a[0]] = a[1]
		else:
			Ans[a[0]] = bisect(ListB, t[0], hi=a[1]) - 1
	print(*Ans[2:])


import sys
import collections
import math
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))

def solve():
	t = int(input())
	for _ in range(t):
		n = int(input())
		tree = [[] for _ in range(n + 1)]
		for i in range(n - 1):
			(p, a, b) = ints()
			tree[p].append((i + 2, a, b))
		prefix = []
		res = ['0'] * (n - 1)

		def dfs(i, a):
			(l, r) = (0, len(prefix) - 1)
			while l <= r:
				m = (l + r) // 2
				if prefix[m] <= a:
					l = m + 1
				else:
					r = m - 1
			res[i - 2] = str(l)
			for child in tree[i]:
				total = child[2]
				if len(prefix) > 0:
					total += prefix[-1]
				prefix.append(total)
				dfs(child[0], a + child[1])
				prefix.pop()
			return
		dfs(1, 0)
		print(' '.join(res))
threading.Thread(target=solve).start()


from bisect import bisect_left, bisect_right
import sys, threading
sys.setrecursionlimit(10 ** 8)
threading.stack_size(10 ** 8)

def solve():
	for _ in range(int(input())):
		n = int(input())
		graph = [[] for i in range(n + 1)]
		for i in range(2, n + 1):
			(u, aj, pj) = map(int, input().split())
			graph[i].append([u, aj, pj])
			graph[u].append([i, aj, pj])
		preaj = [0] * (n + 1)
		maxpath = [0] * (n + 1)
		vis = set()
		vis.add(1)

		def dfs(node, post):
			for i in graph[node[0]]:
				if i[0] not in vis:
					vis.add(i[0])
					preaj[i[0]] = preaj[node[0]] + i[1]
					find = 0
					if len(post) != 0:
						post.append(i[2] + post[-1])
					if len(post) == 0:
						post.append(i[2])
					find = bisect_right(post, preaj[i[0]])
					maxpath[i[0]] = find
					dfs(i, post)
					post.pop()
		dfs([1, 0, 0], [])
		print(*maxpath[2:])
threading.Thread(target=solve).start()


import bisect
import sys

class Node:

	def __init__(self, id):
		self.id = id
		self.root = None
		self.a = 0
		self.b = 0
		self.children = []

def solve(root, n):
	b_cumsum = []
	A = 0
	result = [-1] * n
	queue = [root]
	while queue:
		next_item = queue.pop()
		if isinstance(next_item, int):
			A -= next_item
			b_cumsum.pop()
			continue
		A += next_item.a
		b_cumsum.append((b_cumsum[-1] if b_cumsum else 0) + next_item.b)
		result[next_item.id - 1] = bisect.bisect_right(b_cumsum, A) - 1
		queue.append(next_item.a)
		for child in next_item.children:
			queue.append(child)
	return result[1:]

def main():
	sys.setrecursionlimit(1000000)
	t = int(input())
	for i in range(t):
		vertexes = {}
		n = int(input())
		for j in range(2, n + 1):
			(p, a, b) = [int(v) for v in input().split()]
			if p not in vertexes:
				vertexes[p] = Node(p)
			if j not in vertexes:
				vertexes[j] = Node(j)
			parent = vertexes[p]
			child = vertexes[j]
			child.root = parent
			child.a = a
			child.b = b
			parent.children.append(child)
		res = solve(vertexes[1], n)
		print(*res)
main()


import sys
import threading

def dfs(v, p, pans):
	global put, mb, ans
	(l, r) = (-1, len(mb))
	while r > l + 1:
		m = (r + l) // 2
		if mb[m] > pans:
			r = m
		else:
			l = m
	ans[v] = l + 1
	for i in range(len(put[v])):
		if put[v][i][0] != p:
			if len(mb) != 0:
				mb.append(mb[-1] + put[v][i][1][1])
			else:
				mb.append(put[v][i][1][1])
			dfs(put[v][i][0], v, pans + put[v][i][1][0])
			if len(mb) > 0:
				mb.pop()

def main():
	global put, mb, ans
	for _ in range(int(input())):
		n = int(input())
		put = [list() for _ in range(n)]
		for i in range(1, n):
			(p, a, b) = map(int, input().split())
			put[p - 1].append([i, [a, b]])
		(ans, mb) = ([0] * n, list())
		dfs(0, -1, 0)
		for i in range(1, len(ans)):
			print(ans[i], end=' ')
		print()
sys.setrecursionlimit(10 ** 9)
threading.stack_size(10 ** 8)
thread = threading.Thread(target=main)
thread.start()
thread.join()