Dominating color - MarisaOJ: Marisa Online Judge

Given a tree of

n

$n$ vertices, vertex

i

$i$ has color

A_{i}

$A_i$ . Given

q

$q$ queries of the form

(u, v)

$(u, v)$ , find the dominating color on the simple path from

u

$u$ to

v

$v$ . If the path from

u

$u$ to

v

$v$ containing

k

$k$ edges, color

c

$c$ is called dominating if it appears at least

⌈ \frac{k}{2} ⌉ + 1

$\lceil \frac{k}{2} \rceil + 1$ times. ### Input - The first line contains two integers

n, q

$n, q$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

n - 1

$n-1$ lines, each line contains two integers

u, v

$u, v$ , there is an edge between

u

$u$ and

v

$v$ . - The next

q

$q$ lines, each line contains two integers

u, v

$u,v$ , a query. ### Output - Print the answer for each query, or print

- 1

$-1$ if no answer exists. ### Constraints -

1 \leq n \leq 10^{5}

$1 \le n \le 10^5$ . -

1 \leq A_{i} \leq 10^{9}

$1 \le A_i \le 10^9$ . -

1 \leq u, v \leq n

$1 \le u, v \le n$ . ### Example Input:

431222122324122314

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

Output:

- 122

$-1 2 2$

Square root decomposition
	Frequency
	Tree query
	Inversions query
	Nearest vertex
	Dominating color
	String occurences 3
	Inversions query 2
	Pair
	Sparse update
	Tree
	Range query
	String concatenation
	Subarray distance
	Chameleon
	Knapsack
	Bit counting
	Subsequence queries
	Sub-subsequence
	Delete numbers
	Mode
	Marisa is happy
	Inversions query 3
	Upperbound
	23 path
	Yet another square root decomposition problem
	Marisa plays poker
	Wonderful world

Topic

Tree

Data structure

Rating

1700

Solution (1)

Solution