Mancunian And Colored Tree
Tag(s):

## Tree

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: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, 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