You are given an undirected tree with N nodes and the tree is rooted at node 1. Each node has an integer value A[i] associated with it represented by an array A of size N.
Also, you are given Q queries of the following type:
• uvk: Find the kth smallest value present on the simple path between node u and node v. If the number of nodes on the simple path between node u and node v is less than k, then print —1.
• The first line contains two space-separated integers NQ denoting the number of nodes and queries respectively.
• The second line contains N space-separated integers denoting array A.
• Next N — 1 line contains two space-separated integers denoting the edges of the tree.
• Next Q lines contain three space-separated integers denoting the queries.
Output format
Print Q space-separated integers denoting the answer of queries.
Constraints
1 ≤ N ≤ 4 x 104
1 ≤ Q ≤ 105
1 ≤ A[i] ≤ 109
int query1(int root)
{
if (adj[root].size() == 0)
{
p[root].first += p[root].second;
return 0;
}
int sum = 0;
for (int i = 0; i < adj[root].size(); i++)
{
if (visit[adj[root][i]] == 0)
{
query1(adj[root][i]);
p[root].second += p[adj[root][i]].second;
visit[adj[root][i]] = 1;
}
}
p[root].first += p[root].second;
return 0;
}
Comments
Leave a comment