Colorful Tree | Practice Problems

Colorful Tree

★★★★★

3.8

5 votes

Algorithms, Binary Search, Depth First Search, Graphs, Hard, Sqrt-Decomposition

Details

Submissions

Discussion

Editorial

Problem

You are given a tree that contains $N$ nodes, where every node $i$ is colored with some color $C_i$ .

The distance of a node $V$ from a node $U$ is defined as the number of edges along the simple path from the node $U$ to the node $V$ . Your task is to answer $M$ queries of the following type:

$K$ $C$ : Determine the distance of most distant node of color $C$ from node $K$ . If there is no node of color $C$ in the tree, then print $-1$ .

Input format

First line: Two integers $N$ and $M$
Next line: $N$ space-separated integers, where the $i^{th}$ integer is $C_i$ denoting the color of the $i^{th}$ node
Next $N-1$ lines: Two integers $U$ and $V$ representing an edge between nodes $U$ and $V$
Next $M$ lines: Two integers $K$ and $C$

Output format

For each query, print the distance of most distant node of color $C$ from the node $K$ .
The answer for each query should come in a new line.

Input Constraints

$1 \le N, M \le 5 \times10^5$

$1 \le C_i \le 5 \times10^5$

$1 \le U, V \le N$

$1 \le K \le N$

$1 \le C \le 5 \times10^5$

Sample Input

10 15
2 6 5 99 500000 6 5 3 5 5
1 2
2 10
1 3
3 5
3 6
6 7
1 4
4 8
4 9
3 5
4 5
2 5
6 5
8 500000
5 500000
5 1000
6 6
8 6
5 99
3 6
3 100
9 5
7 5
3 3

Sample Output

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

Tree Corresponding to the Sample — The tree corresponding to the input

Contributers:

Ashish Gupta

Pranjal Jain