I need help with this problem:
There are n states in a country. The states are connected to each other by undirected borders and there are total n-1 boarders between different pairs of states. These borders form a tree. The strength of a border i is str[i].
Each state grows some fruits. Initially, there are no fruits in any states. The rate at which a fruit is grown in city i is R[i] per unit time. A country that is defined as a tree of connected cities is considered rich at an instant if all the states contain at least X fruits.
A company wants to buy these fruits. It buys fruits from the state that contains the lowest production rate in the country and it visits a country only if it is rich. If there are multiple such countries, the company randomly chooses one country and buys from it.
You are required to answer q queries that are represented as follows:
The i-th query consists of three space-separated integers a_i, b_i, c_i. They allow you to generate as D_i, T_i and X_i as D_i=a_i XOR ans_{i-1}, T_i=b_i XOR ans_{i-1} and X_i=c_i XOR ans_{i-1} where ans_i is the answer to i-th query and ans_0=0
At t=0 borders whose strength value is greater than D_i splits apart and the remaining connected states form separate countries. Your task is to determine the total number of fruits that the company can collect at time T_i.
Each query is independent in nature.
You are required to answer these queries online because the input of the next query depends on the answer of the previous query.
Input format
First line: n and q
n-1 lines: Three space-separated integers u, v, w that represent that state u and state v share border whose strength value is w
Next line: n space-separated integers where the i integer is R[i]
q lines: Three space-separated integers that are defined in the question
Output format
For each query, print the answer in a new line.
Constraints
1<=n,q<=200000
0<=str[i],X[i],T[i],D[i]<=100000000
0<=R[i]<=100000
0<=a_i,b_i,c_i<2^62
Input
5 3
1 2 1
2 3 2
3 4 3
4 5 4
1 2 3 4 5
0 2 7
16 17 26
27 19 18
Output
18
27
112
Explanation
first query, since d=0, all cities form individual countries. So min. rate is the same as the max rate for each country since it contains a single city. Cities that can produce at least 7 unit of fruits in 2-time units are city 4 and 5. Answer is (4+5)*2 = 18
second query, d=2, t=3, x=8. d=2 makes 3 countries - first formed by 1--2--3, second consisting of only 4 and third of only 5. Again only 4 and 5 passes the criteria, and the answer is (4+5)*3 = 27
third query, d=0, t=8, x=9. All cities are a separate country. Eligible cities to buy fruit are 2,3,4 and 5. Answer is (2+3+4+5)*8 = 112
I tried to do DFS for every query and block the edges that we can't use in that query, but that solution was to slow as it had O(q*n) time complexity. Can someone please give me some hint on what should I do to solve this problem more efficiently?
Thank you in advance.