Cats and Tree

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/SNCKFL19/hindi/CATS.pdf), [Bengali](http://www.codechef.com/download/translated/SNCKFL19/bengali/CATS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/SNCKFL19/mandarin/CATS.pdf), [Russian](http://www.codechef.com/download/translated/SNCKFL19/russian/CATS.pdf), and [Vietnamese](http://www.codechef.com/download/translated/SNCKFL19/vietnamese/CATS.pdf) as well. You are given a rooted tree with $N$ nodes labelled $1$ through $N$. For each nonroot node $i$, let's denote the direct parent of this node by $p_i$. $N$ cats, also labelled $1$ through $N$, have vanished from Chef's home. The cats are frightened, so they want to climb the tree one by one, in the order $C_1, C_2, \ldots, C_N$. At any time, each node may contain at most one cat. When cat $c$ wants to start climbing the tree, the following happens:  If there is already a cat in node $c$, then cat $c$ leaves and decides to climb another tree. Otherwise, the cat makes a leap to node $c$.  Then, while there is no cat in the parent of this cat's current node, the cat jumps to the parent of its current node. When it is impossible to jump any further (due to reaching the root or finding a cat in the parent node), the cat stays in its current node. Find the number of jumps performed by each cat (including the initial leap to the tree). ### Input  The first line of the input contains a single integer $N$.  The second line contains $N$ spaceseparated integers $p_1, p_2, \ldots, p_N$. The parent of the root will be denoted with a $0$.  The third line contains $N$ spaceseparated integers $C_1, C_2, \ldots, C_N$. ### Output Print $N$ lines. For each valid $i$, the $i$th of these lines should contain a single integer — the number of jumps performed by cat $C_i$. ### Constraints  $1 \le N \le 3 \cdot 10^5$  $0 \le p_i \le N$ for each valid $i$  $C_1, C_2, \ldots, C_N$ form a permutation of $1, 2, \ldots, N$  the graph described on the input is a tree ### Example Input ``` 10 0 1 2 3 3 1 6 6 6 1 5 6 3 4 2 1 7 8 9 10 ``` ### Example Output ``` 4 1 2 2 0 0 1 1 1 1 ``` ### Example Input ``` 7 2 4 0 3 3 3 4 7 6 2 1 4 5 3 ``` ### Example Output ``` 3 1 2 2 0 1 0 ```Author:  bciobanu 
Editorial  https://discuss.codechef.com/problems/CATS 
Tags  bciobanu, binarylifting, easymedium, snckfl19 
Date Added:  9022019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 