Path Queries

3

4 votes
Algorithms, Trees, C++, Graphs, Depth First Search
Problem

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:

  • u v: Find the value of Minimum + Maximum + Median of all the values present on the simple path between node u and node v
  • Suppose, K nodes are present on the simple path, then Median is defined as ((K+1)/2)th smallest element present on the simple path.

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 N1 lines contain two space-separated integers denoting the edges of the tree.
  • Next Q lines contain two space-separated integers denoting the queries.

Output format

Print Q space-separated integers denoting the answer of queries.

Constraints

1N4×1041Q1051A[i]106

 

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation
  • Simple path between node 8 and node 7 is  8 - 4 - 1 -  3 - 7.
  • Values of nodes present on the simple path is [7, 3, 105, 9, 7].
  • Minimum Value = 3
  • Maximum Value = 105
  • Median Value = 7
  • Hence, required answer is = 105 + 3 + 7 = 115.
Editor Image

?