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

View as PDF

Points: 7 (partial)
Time limit: 2.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 node having value . 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 , it rounds down, and rounds up otherwise.

For example, rounds to , and rounds to .

#### Input Specification

The first line of input will contain two integers, and .
The second line of input will contain space separated integers, .
The next lines will have two integers, and , indicating there is an edge between and . The next lines will each contain a valid query.

#### Output Specification

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 nodes, so the mean is , which is rounded to .

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

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

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