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^{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 \leq N \leq 1 000$

$1 \le a_i, b_i \le N$ $1 \leq a_{i}, b_{i} \leq N$

$1 \le Q \le 1\,000$ $1 \leq Q \leq 1 000$

$1 \le v_i \le 100\,000$ $1 \leq v_{i} \leq 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

Copy

Sample Output

Copy

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.