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

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Kirito, jyzh1248

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}$ ~i^\text{th}~ node having value $v_i$ ~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$ ~0.5~, it rounds down, and rounds up otherwise.

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

Constraints

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

$1 \le a_i, b_i \le N$ ~1 \le a_i, b_i \le N~

$1 \le Q \le 1\,000$ ~1 \le Q \le 1\,000~

$1 \le v_i \le 100\,000$ ~1 \le v_i \le 100\,000~

Input Specification

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

Output Specification

$Q$ ~Q~ lines, the answer to each query.

Sample Input

Sample Output

Explanation for Sample Output

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

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

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

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

Comments

-17

CoolNoobyBooby commented on April 15, 2018, 5:37 p.m. ← edit 12 →

2.5 rounds to 3, and 4.48 rounds to 4 What if the number is 4.499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999?

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.