All Tracks Problem

The Great KL
Tag(s):

Greedy, Medium, Trees

Problem
Editorial
Analytics

View Russian Translation

The Great KL lives in city KLand. KLand has n junctions and n-1 bidirectional roads. One can reach any city from any other city using only these roads.

Each junction has a cupid in it. Cupids are of m different types. Type of the cupid in junction i is ci. KL wants to know for each of m types that what is the maximum distance between two cupids of that type. Distance between two junctions is the length of their shortest path (number of roads in the shortest path between them).

KL is not that smart and can't figure this out himself. Please help him!

Input

The first line of input contains two integers n and m (1 ≤ m ≤ n ≤ 105).

The second line contains n integers c1, c2, ..., cn separated by spaces (1 ≤ ci ≤ m).

The next n-1 lines contain the roads. Each line contains two integers v and u; Endpoints of a road (1 ≤ v, u ≤ n).

For each i between 1 to m there is at least one cupid whit that type.

Output

Print m integers in one line; i-th of them should be the answer for cupid-type i.

SAMPLE INPUT
4 2
1 1 1 2
1 4
1 3
2 3

SAMPLE OUTPUT
2 0 
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?