Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese].

In Chefland, there are $N$ cities (numbered $1$ through $N$) connected by $N-1$ bidirectional roads. Each city has exactly one garden. For each valid $i$, let's denote the population of the $i$-th city by $A_{i}$ and the initial number of fruits in its garden by $B_{i}$; also, at any time, let's denote the current number of fruits in its garden by $F_{i}$ ($F_{i} = B_{i}$ initially).

You are given a permutation $P$ of the integers $1$ through $N$. For each $i$ ($1 ≤ i ≤ N$), during the $i$-th of the next $N$ days, the people of the city $P_{i}$ do the following:
1. For each city $j$ which is reachable from the city $P_{i}$ (including the city $P_{i}$ itself), visit the city $j$ and consume $\mathrm{min}(A_{P_{i}}, F_{j})$ fruits from the garden of the city $j$; afterwards, $F_{j}$ decreases by $\mathrm{min}(A_{P_{i}}, F_{j})$.
2. Return to the city $P_{i}$ and cut off all the roads that are connecting it to other cities, so that nobody can visit the city $P_{i}$ or visit any other city from their city if it requires passing through the city $P_{i}$.

For each valid $i$, let $D_{i}$ be the first day when the number of fruits in the $i$-th city's garden becomes zero, or $-1$ if the fruits in its garden never end up all eaten. Find $D_{1}, D_{2}, \ldots, D_{N}$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.
The next line contains $N$ space-separated integers $P_{1}, P_{2}, \ldots, P_{N}$.
The next line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
The last line contains $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$.

------  Output ------
For each test case, print a single line containing $N$ space-separated integers $D_{1}, D_{2}, \ldots, D_{N}$.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ u, v ≤ N$
$1 ≤ P_{i} ≤ N$ for each valid $i$
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (30 points):
$N ≤ 10^{3}$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{3}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2

3

1 2

2 3

1 2 3

1 2 3

1 3 6

3

1 2

1 3

1 2 3

5 6 3

4 10 12
----- Sample Output 1 ------ 
1 2 3

1 2 -1
----- explanation 1 ------ 
Example case 1: The process is as follows:
- On day $1$, people from city $1$ eat $1$ fruit from each garden. Afterwards, there are $[0, 2, 5]$ fruits in the gardens of cities $[1, 2, 3]$ respectively, so the answer for city $1$ is $1$, since the number of fruits in this garden becomes zero on day $1$.
- Then, on day $2$, people from city $2$ eat $2$ fruits from each of the gardens in cities $2$ and $3$. Afterwards, there are $0$ fruits in the garden of city $2$ (so the answer for city $2$ is $2$, since the number of fruits in this garden becomes zero on this day) and $3$ fruits in the garden of city $3$.
- Finally, on day $3$, people from city $3$ eat $3$ fruits from the garden of city $3$, so the answer for city $3$ is $3$.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Sorting

Range queries

Complete search

Tree algorithms

Spanning trees

Data structures
Skill types: Sorting

Data structures

Range queries

Complete search

Starter code:

Solutions:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
from bisect import bisect_left as Lower_Bound

def create_new():
	check = dict()
	for i in range(n - 1, -1, -1):
		parent[pi[i]] = pi[i]
		for j in Graph[pi[i]]:
			if j in check:
				z = find(j)
				parent[z] = pi[i]
				newGraph[pi[i]].append(z)
				newGraph[z].append(pi[i])
		check[pi[i]] = 'Present'

def DFS(x):
	visited.add(x)
	days_Stack.append(Trackdays[x])
	if ai_Stack == []:
		ai_Stack.append(ai[x])
	else:
		ai_Stack.append(ai_Stack[-1] + ai[x])
	z = Lower_Bound(ai_Stack, bi[x])
	if z < len(days_Stack):
		ans[x] = days_Stack[z]
	for i in newGraph[x]:
		if i not in visited:
			DFS(i)
	days_Stack.pop(-1)
	ai_Stack.pop(-1)

def find(x):
	if x == parent[x]:
		return x
	z = find(parent[x])
	parent[x] = z
	return z
t = int(input())
for you in range(t):
	n = int(input())
	Graph = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		Graph[u - 1].append(v - 1)
		Graph[v - 1].append(u - 1)
	pi = [int(i) - 1 for i in input().split()]
	ai = [int(i) for i in input().split()]
	bi = [int(i) for i in input().split()]
	newGraph = [[] for i in range(n)]
	parent = [-1 for i in range(n)]
	create_new()
	Trackdays = dict()
	for i in range(n):
		Trackdays[pi[i]] = i + 1
	ans = [-1 for i in range(n)]
	visited = set()
	days_Stack = list()
	ai_Stack = list()
	DFS(pi[0])
	print(*ans)


import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
sys.setrecursionlimit(10 ** 6)

def find(u):
	if P[u] == u:
		return u
	else:
		P[u] = find(P[u])
		return P[u]

def unite(u, v):
	v = find(v)
	P[v] = u
	T[u].append(v)

def dfs(u):
	if len(prefix):
		prefix.append(a[u] + prefix[-1])
	else:
		prefix.append(a[u])
	path.append(pos[u])
	t = bl(prefix, b[u])
	if t == len(prefix):
		ans[u] = -2
	else:
		ans[u] = path[t]
	for v in T[u]:
		dfs(v)
	path.pop()
	prefix.pop()
for _ in range(int(input())):
	n = int(input())
	adj = dd(list)
	T = dd(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	P = [i for i in range(n)]
	ans = [-1 for i in range(n)]
	pos = [0 for i in range(n)]
	present = [0 for i in range(n)]
	prefix = []
	path = []
	for i in range(n - 1, -1, -1):
		p[i] -= 1
		pos[p[i]] = i
		for j in adj[p[i]]:
			if present[j]:
				unite(p[i], j)
		present[p[i]] = 1
	dfs(p[0])
	for i in range(n):
		ans[i] += 1
	print(*ans)


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

def DFS(x):
	visited[x] = 1
	q.append(whichday[x])
	if pref == []:
		pref.append(ai[x])
	else:
		pref.append(pref[-1] + ai[x])
	z = bisect.bisect_left(pref, bi[x])
	if z < len(q):
		ans[x] = q[z]
	for i in adjnew[x]:
		if visited[i] == 0:
			DFS(i)
	q.pop(-1)
	pref.pop(-1)

def find(x):
	if x == parent[x]:
		return x
	z = find(parent[x])
	parent[x] = z
	return z
t = int(input())
for you in range(t):
	n = int(input())
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		l = input().split()
		u = int(l[0])
		v = int(l[1])
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	p = input().split()
	pi = [int(i) - 1 for i in p]
	a = input().split()
	ai = [int(i) for i in a]
	b = input().split()
	bi = [int(i) for i in b]
	adjnew = [[] for i in range(n)]
	parent = [-1 for i in range(n)]
	hashi = dict()
	whichday = dict()
	for i in range(n):
		whichday[pi[i]] = i + 1
	ans = [-1 for i in range(n)]
	for i in range(n - 1, -1, -1):
		parent[pi[i]] = pi[i]
		for j in adj[pi[i]]:
			if j in hashi:
				z = find(j)
				parent[z] = pi[i]
				adjnew[pi[i]].append(z)
				adjnew[z].append(pi[i])
		hashi[pi[i]] = 1
	visited = [0 for i in range(n)]
	q = []
	pref = []
	DFS(pi[0])
	for i in range(n):
		print(ans[i], end=' ')
	print()