This is the hard version of the problem. The only difference is that, in this version, K_{i} ≤ 10^{18}.

There’s a [tree] having N nodes, out of which, some nodes are energetic.

Initially, energy of all the nodes is 0. In the i^{th} second, every energetic node will make the energy of itself and all its neighbours increase by i.

You need to answer Q queries. For the i^{th} query, you are given three integers: 
 
X_{i} T_{i} K_{i} : Find the minimum number of seconds after which, there are at least T_{i} nodes with energy not less than K_{i} on the path from node 1 to node X_{i}. If it is not possible to have at least T_{i} nodes with energy not less than K_{i} on the path from node 1 to node X_{i} after any amount of time, print -1 instead.

------ Input Format ------ 

- The first line contains an integer N — the number of nodes.
- The second line contains N space-separated integers, the array A denoting whether the nodes are energetic. If A_{i} = 1, it means that the i^{th} node is energetic, otherwise the i^{th} node is not energetic.
- The next N-1 lines describe the edges. The i^{th} of these N-1 lines contains two space-separated integers U_{i} and V_{i}, denoting an edge between U_{i} and V_{i}.
- The next line contains an integer Q — the number of queries.
- The next Q lines contain three space-separated integers X_{i},T_{i},K_{i}, the query.

------ Output Format ------ 

For each query, output on a new line: the minimum number of seconds after which, there are at least T_{i} nodes with energy not less than K_{i} on the path from node 1 to node X_{i}.  
If it is not possible to have at least T_{i} nodes with energy not less than K_{i} on the path from node 1 to node X_{i} after any amount of time, print -1 instead.

------ Constraints ------ 

$1 ≤ N,Q ≤ 4\cdot 10^{4}$
$0 ≤ A_{i}≤ 1$
$1 ≤ U_{i}, V_{i},X_{i},T_{i} ≤ N$
$1 ≤ K_{i} ≤ 10^{18}$

----- Sample Input 1 ------ 
7
1 0 1 0 0 1 0
1 2
1 3
1 4
3 5
3 6
4 7
4
7 3 1
6 3 2
7 2 3
5 3 5
----- Sample Output 1 ------ 
-1
1
2
3
----- explanation 1 ------ 
Query $1$: No matter how long, there will not be at least $3$ nodes having energy not less than $1$ on the path from node $1$ to node $7$. Thus, the answer is $-1$.

Query $2$: In the $1^{st}$ second, the energy of nodes $1,3,$ and $6$ becomes $2,3,$ and $2$ respectively. Thus, there are at least $3$ nodes with energy not less than $2$.

Query $3$: In the $2^{nd}$ second, the energy of nodes $1,4,$ and $7$ becomes $6,3,$ and $0$ respectively. Thus, there are at least $2$ nodes with energy not less than $3$.

Query $4$: In the $3^{rd}$ second, the energy of nodes $1,3,$ and $5$ is $12,18,$ and $6$ respectively. Thus, there are at least $3$ nodes with energy not less than $5$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Sorting

Range queries

Complete search

Segment trees revisited

Tree algorithms

Data structures


Solutions:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 5)
inp = lambda : list(map(int, input().split()))

class fenwicktree:

	def __init__(self, n):
		self.BITTree = [0] * (n + 1)
		self.size = n

	def getsum(self, i):
		s = 0
		i = i + 1
		while i > 0:
			s += self.BITTree[i]
			i -= i & -i
		return s

	def query(self, l, r):
		return self.getsum(r) - self.getsum(l - 1)

	def update(self, i, v):
		i += 1
		while i <= self.size:
			self.BITTree[i] += v
			i += i & -i

def dfs(p, prev):
	v = a[p - 1]
	for i in child[p]:
		v += a[i - 1]
	count.update(v, 1)
	for i in child[p]:
		if i == prev:
			continue
		dfs(i, p)
	for i in take[p]:
		(t, k, ind) = i
		(l, h) = (0, n)
		point = -1
		while l <= h:
			mid = (l + h) // 2
			if count.query(n - mid, n) < t:
				l = mid + 1
			else:
				point = n - mid
				h = mid - 1
		if point == -1:
			continue
		c = point
		(l, h) = (0, k)
		while l <= h:
			mid = (l + h) // 2
			val = c * (mid * (mid + 1) // 2)
			if val < k:
				l = mid + 1
			else:
				ans[ind] = mid
				h = mid - 1
	for i in take[p]:
		(t, k, ind) = i
	count.update(v, -1)
for T in range(1):
	n = int(input())
	a = inp()
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = inp()
		child[u].append(v)
		child[v].append(u)
	take = [[] for i in range(n + 1)]
	m = int(input())
	for q in range(m):
		(x, t, k) = inp()
		take[x].append([t, k, q])
	ans = [-1 for i in range(m)]
	count = fenwicktree(n + 1)
	dfs(1, 0)
	print(*ans, sep='\n')