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

Question #280901

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.


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 104

1 ≤ Q ≤ 105

1 ≤ A[i] ≤ 109

1
Expert's answer
2021-12-20T10:01:39-0500
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;
}

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog