Nearest vertex - MarisaOJ: Marisa Online Judge

Given a tree of

$n$ vertices. Vertex

$i$ has number

$A_i$ on it. You are also given

$q$ queries of the form

$u, x$ , find the distance of the nearest vertex having value

$x$ on it to

$u$ . ### Input - The first line contains two integers

$n, q$ . - The second line contains

$n$ integers

$A_i$ . - The next

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

$u, v$ , there is an edge between

$u$ and

$v$ . - The next

$q$ lines, each line contains two integers

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

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

$1 \le n, q \le 5 \times 10^4$ . -

$1 \le A_i, x \le n$ . ### Example Input:

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

Output:

$0 1$

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

Graph

Shortest path

Data structure

Rating

1600

Solution (2)

Solution