Answer to Question #280901 in C++ for Rahul Sigh

Question

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 k^th 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.

Input format

•  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 10⁴

¹ ≤ Q ≤ 10⁵

1 ≤ A[i] ≤ 10⁹

Answer 1

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;
}