Squirrel's New Home

Problem Source

JLOI2014

Problem Description

The squirrel's new home is a tree. It was just decorated: the home has $n$ rooms connected by $n - 1$ branches, every two rooms are reachable from each other, and the path between any two rooms is unique. My, he really lives in a "tree".

The squirrel wants to invite the little cat to visit, and he has prepared a visiting guide: the cat should visit $a_1$, then $a_2$, $\dots$, and finally $a_n$ in that order. But following the guide means walking through many rooms repeatedly, and the lazy cat keeps refusing. The squirrel tells him: every time you arrive at a room, you may take a candy from it. The greedy cat immediately agrees.

Now the squirrel wants to know: to make sure the cat always has a candy to take, what is the minimum number of candies he must place in each room?

Note that the last room $a_n$ in the guide is the restaurant, where a big meal is prepared. So when the cat finally arrives at the restaurant, it does not need to take a candy.

Input Format

The first line contains a positive integer $n$ ($1 \le n \le 3 \times 10^5$), the number of rooms. The second line contains $n$ positive integers describing $a_1, a_2, \dots, a_n$.

The following $n - 1$ lines each contain two positive integers $x, y$, meaning rooms $x$ and $y$ are connected by a branch.

Output Format

Output $n$ lines in total; the $i$-th line outputs the minimum number of candies that must be placed in room $i$ so the cat always has one to take.

Sample Input

5
1 4 5 3 2
1 2
2 4
2 3
4 5

Sample Output

1
2
1
2
1