Beech Tree

문제

Vétyem Woods is a famous woodland with lots of colorful trees. One of the oldest and tallest beech trees is called Ős Vezér.

The tree Ős Vezér can be modeled as a set of $NN$ nodes and $N-1N-1$ edges. Nodes are numbered from $00$ to $N-1N-1$ and edges are numbered from $11$ to $N-1N-1$. Each edge connects two distinct nodes of the tree. Specifically, edge $ii$ ($1\le i<N1\; \backslash le\; i\; \backslash lt\; N$) connects node $ii$ to node $P[i]P[i]$, where $0\le P[i]<i0\; \backslash le\; P[i]\; \backslash lt\; i$. Node $P[i]P[i]$ is called the parent of node $ii$, and node $ii$ is called a child of node $P[i]P[i]$.

Each edge has a color. There are $MM$ possible edge colors numbered from $11$ to $MM$. The color of edge $ii$ is $C[i]C[i]$. Different edges may have the same color.

Note that in the definitions above, the case $i=0i\; =\; 0$ does not correspond to an edge of the tree. For convenience, we let $P[0]=-1P[0]\; =\; -1$ and $C[0]=0C[0]\; =\; 0$.

For example, suppose that Ős Vezér has $N=18N\; =\; 18$ nodes and $M=3M\; =\; 3$ possible edge colors, with $1717$ edges described by connections $P=[-1,0,0,0,1,1,1,2,2,3,3,3,4,4,5,10,11,11]P\; =\; [-1,\; 0,\; 0,\; 0,\; 1,\; 1,\; 1,\; 2,\; 2,\; 3,\; 3,\; 3,\; 4,\; 4,\; 5,\; 10,\; 11,\; 11]$ and colors $C=[0,1,2,3,1,2,3,1,3,3,2,1,1,2,2,1,2,3]C\; =\; [0,\; 1,\; 2,\; 3,\; 1,\; 2,\; 3,\; 1,\; 3,\; 3,\; 2,\; 1,\; 1,\; 2,\; 2,\; 1,\; 2,\; 3]$. The tree is displayed in the following figure:

Árpád is a talented forester who likes to study specific parts of the tree called subtrees. For each $rr$ such that $0\le r<N0\; \backslash le\; r\; \backslash lt\; N$, the subtree of node $rr$ is the set $T(r)T(r)$ of nodes with the following properties:

• Node $rr$ belongs to $T(r)T(r)$.
• Whenever a node $xx$ belongs to $T(r)T(r)$, all children of $xx$ also belong to $T(r)T(r)$.
• No other nodes belong to $T(r)T(r)$.

The size of the set $T(r)T(r)$ is denoted as $\mathrm{\mid }T(r)\mathrm{\mid }|T(r)|$.

Árpád recently discovered a complicated but interesting subtree property. Árpád's discovery involved a lot of playing with pen and paper, and he suspects you might need to do the same to understand it. He will also show you multiple examples you can then analyze in detail.

Suppose we have a fixed $rr$ and a permutation $v_0,v_1,\dots ,v_{\mathrm{\mid }T(r)\mathrm{\mid }-1}v\_0,\; v\_1,\; \backslash ldots,\; v\_\{|T(r)|-1\}$ of the nodes in the subtree $T(r)T(r)$.

For each $ii$ such that $1\le i<\mathrm{\mid }T(r)\mathrm{\mid }1\; \backslash le\; i\; \backslash lt\; |T(r)|$, let $f(i)f(i)$ be the number of times the color $C[v_i]C[v\_i]$ appears in the following sequence of $i-1i-1$ colors: $C[v_1],C[v_2],\dots ,C[v_{i-1}]C[v\_1],\; C[v\_2],\; \backslash ldots,\; C[v\_\{i-1\}]$.

(Note that $f(1)f(1)$ is always $00$ because the sequence of colors in its definition is empty.)

The permutation $v_0,v_1,\dots ,v_{\mathrm{\mid }T(r)\mathrm{\mid }-1}v\_0,\; v\_1,\; \backslash ldots,\; v\_\{|T(r)|-1\}$ is a beautiful permutation if and only if all the following properties hold:

• $v_0=rv\_0\; =\; r$.
• For each $ii$ such that $1\le i<\mathrm{\mid }T(r)\mathrm{\mid }1\; \backslash le\; i\; \backslash lt\; |T(r)|$, the parent of node $v_{i}v\_i$ is node $v_{f(i)}v\_\{f(i)\}$.

For any $rr$ such that $0\le r<N0\; \backslash le\; r\; \backslash lt\; N$, the subtree $T(r)T(r)$ is a beautiful subtree if and only if there exists a beautiful permutation of the nodes in $T(r)T(r)$. Note that according to the definition every subtree which consists of a single node is beautiful.

Consider the example tree above. It can be shown that the subtrees $T(0)T(0)$ and $T(3)T(3)$ of this tree are not beautiful. The subtree $T(14)T(14)$ is beautiful, as it consists of a single node. Below, we will show that the subtree $T(1)T(1)$ is also beautiful.

Consider the sequence of distinct integers $[v_0,v_1,v_2,v_3,v_4,v_5,v_6]=[1,4,5,12,13,6,14][v\_0,\; v\_1,\; v\_2,\; v\_3,\; v\_4,\; v\_5,\; v\_6]\; =\; [1,\; 4,\; 5,\; 12,\; 13,\; 6,\; 14]$. This sequence is a permutation of the nodes in $T(1)T(1)$. The figure below depicts this permutation. The labels attached to the nodes are the indices at which those nodes appear in the permutation.

Clearly, the above sequence is a permutation of the nodes in $T(1)T(1)$. We will now verify that it is beautiful.

• $v_0=1v\_0\; =\; 1$.
• $f(1)=0f(1)\; =\; 0$ since $C[v_1]=C[4]=1C[v\_1]\; =\; C[4]\; =\; 1$ appears $00$ times in the sequence $[][]$.
  • Correspondingly, the parent of $v_{1}v\_1$ is $v_{0}v\_0$. That is, the parent of node $44$ is node $11$. (Formally, $P[4]=1P[4]\; =\; 1$.)
• $f(2)=0f(2)\; =\; 0$ since $C[v_2]=C[5]=2C[v\_2]\; =\; C[5]\; =\; 2$ appears $00$ times in the sequence $[1][1]$.
  • Correspondingly, the parent of $v_{2}v\_2$ is $v_{0}v\_0$. That is, the parent of $55$ is $11$.
• $f(3)=1f(3)\; =\; 1$ since $C[v_3]=C[12]=1C[v\_3]\; =\; C[12]\; =\; 1$ appears $11$ time in the sequence $[1,2][1,\; 2]$.
  • Correspondingly, the parent of $v_{3}v\_3$ is $v_{1}v\_1$. That is, the parent of $1212$ is $44$.
• $f(4)=1f(4)\; =\; 1$ since $C[v_4]=C[13]=2C[v\_4]\; =\; C[13]\; =\; 2$ appears $11$ time in the sequence $[1,2,1][1,\; 2,\; 1]$.
  • Correspondingly, the parent of $v_{4}v\_4$ is $v_{1}v\_1$. That is, the parent of $1313$ is $44$.
• $f(5)=0f(5)\; =\; 0$ since $C[v_5]=C[6]=3C[v\_5]\; =\; C[6]\; =\; 3$ appears $00$ times in the sequence $[1,2,1,2][1,\; 2,\; 1,\; 2]$.
  • Correspondingly, the parent of $v_{5}v\_5$ is $v_{0}v\_0$. That is, the parent of $66$ is $11$.
• $f(6)=2f(6)\; =\; 2$ since $C[v_6]=C[14]=2C[v\_6]\; =\; C[14]\; =\; 2$ appears $22$ times in the sequence $[1,2,1,2,3][1,\; 2,\; 1,\; 2,\; 3]$.
  • Correspondingly, the parent of $v_{6}v\_6$ is $v_{2}v\_2$. That is, the parent of $1414$ is $5

As we could find a beautiful permutation of the nodes in $T(1)T(1)$, the subtree $T(1)T(1)$ is indeed beautiful.

Your task is to help Árpád decide for every subtree of Ős Vezér whether it is beautiful.