Problems
Tree
Tree
The hanging tree contains $n\:(1 \le n \le 10^6)$ vertices. Each vertex is colored in one of $n$ colors. For each vertex $v$ find the number of different colors, occurring in the subtree with root $v$.
\InputFile
The first line contains the number $n$. The next $n$ lines describe the vertices. The description of the vertex $i$ has the form $p_i\:c_i$, where $p_i$ is the parent number of the vertex $i$, and $c_i$ is the color of the vertex $i\:(1 \le c_i \le n)$. For the root of the tree $p_i = 0$.
\OutputFile
Print $n$ numbers, denoting the number of different colors in the subtrees rooted at the vertices $1, 2, ..., n$.
\includegraphics{https://eolympusercontent.com/images/r241c0gc3910nee7ipo0t5pp48.gif}
Input example #1
5 2 1 3 2 0 3 3 3 2 1
Output example #1
1 2 3 1 1