René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Boleyn salary (Python or cpp only)","articleBody":"Hey? Everyone... Help me with this problem.\r\n\r\nBoleyn Su runs a company called Acme. There are N employees in the company, and each one of them is represented by a unique employee id whose range lies in [1, N]. Being the head of company, Boleyn's employee id is 1.\r\n\r\nEach employee, except Boleyn, has exactly one direct superior. This means that the hierarchial structure of the company is like a tree, where\r\n\r\nBoleyn, employee id 1, represents the root node.\r\nEach pair of employee is directly or indirectly connected to one another.\r\nThere is no cycle.\r\nLet's represent the salary by the array s = {s[1], s[2], s[3]..., s[N]}, where s[i] is the salary of the ith employee. Salary structure in the company is non-uniform. Even a subordinate may get a higher salary than her superior. Some of the employees in Acme are curious about who gets the kth lowest salary among her subordinates. Help them in solving their query.\r\n\r\nNote\r\n\r\n1st lowest salary is equivalent to lowest salary, 2nd lowest means lowest salary which is greater that 1st lowest salary, and so on.\r\nSalary of each employee is different.\r\nIt is not necessary that the people who are placed higher on hierarchy will have a greater salary than their subordinates.\r\nInput Format\r\nThe first line contains two space separated integers, N Q, where N is the number of employees in Acme, and Q is the number of queries.\r\nThen follows N-1 lines. Each of these lines contain two space separated integers, u p, where p is the superior of u. u and p are employees id.\r\nIn the next line there are N space separated integers, s[1] s[2] ... s[n], where s[i], i ∈ [1..N], is the salary of ith employee.\r\nThen, Q queries follow. Each query contains two space separated integers, v k. See output format for it's definition.\r\n\r\nOutput format\r\nFor the first query, print the id of employee who has the kth lowest salary among the subordinates of v.\r\nFor the subsequent queries, we need to find the kth lowest salary of the subordinates of v+d, where d is the answer of previous query.\r\n\r\nConstraints\r\n1 ≤ N ≤ 3*104\r\n1 ≤ Q ≤ 3*104\r\n1 ≤ s[ i ] ≤ 109, i ∈ [1..N]\r\ns[ i ]  ≠ s[ j ], 1 ≤ i \u003c j ≤ N\r\n1 ≤ u, p ≤ N, u ≠ p\r\n-N ≤ d ≤ N\r\nFor 1st query, 1 ≤ v ≤ N\r\nFor later queries, 1 ≤ v+d ≤ N\r\nFor each query, 1 ≤ K ≤ Number_of_subordinates\r\n\r\nSample Input\r\n\r\n8 7\r\n2 1\r\n3 2\r\n4 2\r\n7 4\r\n8 4\r\n5 1\r\n6 5\r\n70 40 60 80 10 20 30 50\r\n2 1\r\n-6 5\r\n-4 1\r\n-5 3\r\n2 1\r\n-5 4\r\n2 2\r\nSample Output\r\n\r\n7\r\n8\r\n7\r\n3\r\n6\r\n2\r\n8","author":{"url":"https://github.com/ArmanKumar21","@type":"Person","name":"ArmanKumar21"},"datePublished":"2022-10-15T13:49:05.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":4},"url":"https://github.com/116/python-cpp-html-programs-projects/issues/116"}