All Tracks Data Structures Trees Binary/ N-ary Trees Problem

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 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications