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

View as PDF

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

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 .

• commented on April 15, 2018, 1:37 p.m. edit 12

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on April 16, 2018, 10:22 a.m.

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

• commented on Feb. 22, 2018, 2:38 p.m.

This question is worth 5 points?

• commented on April 7, 2018, 2:14 p.m.

no,7