DMOPC '17 Contest 4 P2 - A Heavy Light Decomposition Problem

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type

A tree is a graph where each node is connected to each other, and there is exactly one path between any two nodes. One day, Jessica gives Roger a tree, with the i^\text{th} node having value v_i. She then asks 3 types of queries:

  • 1 x y: Find the mean of all the values of the nodes on the path from x to y, rounded to the nearest integer.
  • 2 x y: Find the median of all the values of the nodes on the path from x to y, rounded to the nearest integer.
  • 3 x y: Find the mode of all the values of the nodes on the path from x to y. In the case of a tie, print the smallest value.

Note: The rules of rounding are as follows: if the decimal part of the number is less than 0.5, it rounds down, and rounds up otherwise.

For example, 2.5 rounds to 3, and 4.48 rounds to 4.

Constraints

1 \le N \le 1\,000

1 \le a_i, b_i \le N

1 \le Q \le 1\,000

1 \le v_i \le 100\,000

Input Specification

The first line of input will contain two integers, N and Q.
The second line of input will contain N space separated integers, v_1, v_2, \dots, v_N.
The next N-1 lines will have two integers, a_i and b_i, indicating there is an edge between a_i and b_i.
The next Q lines will each contain a valid query.

Output Specification

Q lines, the answer to each query.

Sample Input

4 4
1 2 3 3
1 2
2 3
3 4
1 1 4
2 2 4
3 1 4
3 1 2

Sample Output

2
3
3
1

Explanation for Sample Output

For the first query, we pass through all 4 nodes, so the mean is (1+2+3+3)/4=2.25, which is rounded to 2.

For the second query, we pass through the nodes of weight 2, 3, and 3, so their median is 3.

For the third query, we pass through all 4 nodes. 1 and 2 appear only once but 3 appears twice, so the mode is 3.

For the last query, we pass through the first two nodes with weight 1 and 2. Both appear only once, but 1<2, so the mode is 1.


Comments


  • -17
    CoolNoobyBooby  commented on April 15, 2018, 5:37 p.m. edit 12

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 8
      Kirito  commented on April 16, 2018, 2:22 p.m.

      That's still less than 4.5, so it rounds down.