Little IR12660 is gone meeting with a friend flying in from Nice. He has a lot of catching up to do over a good cup of joe and pretzels, so he is unavailable to solve the following problem. Please, do it in his stead:
You are given a tree with $$$N$$$ ($$$1 \le N \le 100\,000$$$) nodes and $$$N - 1$$$ edges. Each node is attributed a color, which we will conveniently label with numbers from $$$1$$$ to $$$K$$$ ($$$1 \le K \le N$$$). We define a chain as a set of nodes that lie on the minimum length path between two nodes. We call these two nodes the endpoints of the chain. Then, we define a correct chain arrangement as a set of chains such that:
For such a correct chain arrangement, let it be called $$$A$$$, we define $$$d_u$$$ as the number of chains in $$$A$$$ of which node $$$u$$$ is part of. More formally, $$$d_u = card(\{ C \,\,\, | \,\, C \subset A, u \in C \})$$$, where $$$card(S)$$$ denotes the number of elements in that set.
Determine the lexicographically maximal array $$$A_V = [d_1, d_2, .. , d_N]$$$ such that there exists a correct chain arrangement $$$A$$$ that yields it.
You are given $$$K$$$ ($$$1 \le K \le N$$$) and $$$N$$$ ($$$1 \le N \le 100\,000$$$).
On the next line, you are given $$$N$$$ numbers, the $$$i$$$-th of which denotes $$$c_i$$$ ($$$1 \le c_i \le N$$$), the color of the i-th node. Within the tests used, every color has at least one node that contains it.
Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N, u \neq v$$$), meaning that there is an edge between $$$u$$$ and $$$v$$$ in the tree.
Print $$$N$$$ numbers, forming the lexicographically maximal array that could be generated by a correct chain arrangement
3 7 1 1 3 2 2 1 2 5 1 5 3 1 4 1 7 3 6 3 2
2 1 2 1 2 0 0
The chains used in the first example are as follows:
