Problem 4 (Binary/N-ary Tree)

After a hectic week at work,Mancunian and Liverbirddecide to go on a fun weekend camping trip. As they were passing through a forest, they stumbled upon a

unique tree of N nodes. Verticesare numbered from 1 to N.

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

Input format

The firstline contains two integers N and C denoting the numberof vertices in the tree and the number of possible colours.

The second line contains N1integers. The ith integer denotes the parent of the i+1th vertex.

The third line containsN integers, denotingthe colours of the vertices. Each colour lies between 1 and C inclusive.

Output format

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

Constraints

• 1N100,000
• 1C100,000

Sample Input

54

11 3 3

1 4 2 1 2

Sample Output

-1-1 -1 1 3

Answer rating: 100% (QA)

Your problem involves finding the closest ancestor of each node in a colored tree that shares the same color The tree is rooted at vertex 1 and colors ... View the full answer