Mancunian And Colored Tree
Tag(s):

## Easy, Trees

Problem
Editorial
Analytics

After a hectic week at work, Mancunian and Liverbird decide to go on a fun weekend camping trip. As they were passing through a forest, they stumbled upon a unique tree of $N$ nodes. Vertices are numbered from $1$ to $N$.

Each node of the tree is assigned a color (out of $C$ possible colors). Being bored, they decide to work together (for a change) and test their reasoning skills. The tree is rooted at vertex $1$. For each node, they want to find its closest ancestor having the same color.

### Input format

The first line contains two integers $N$ and $C$ denoting the number of vertices in the tree and the number of possible colors.
The second line contains $N-1$ integers. The $i \ th$ integer denotes the parent of the $i+1 \ th$ vertex.
The third line contains $N$ integers, denoting the colors of the vertices. Each color lies between $1$ and $C$ inclusive.

### Output format

Print $N$ space-separated integers. The $ith$ integer is the vertex number of lowest ancestor of the $ith$ node which has the same color. If there is no such ancestor, print $-1$ for that node.

### Constraints

• $1 \le N \le 100,000$
• $1 \le C \le 100,000$
SAMPLE INPUT
5 4
1 1 3 3
1 4 2 1 2
SAMPLE OUTPUT
-1 -1 -1 1 3
Explanation

Vertices $1$, $2$ and $3$ do not have any ancestors having the same color as them. The nearest required ancestors for vertices $4$ and $5$ are vertices $1$ and $3$ respectively.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

August Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > Graphs
• Math > Number Theory
• Algorithms > Graphs
• Algorithms > String Algorithms