All Tracks Algorithms Graphs Depth First Search Problem

Restoring trees
/

Algorithms, Depth First Search, Depth-first search, Easy-Medium, Graph

Problem
Editorial
Analytics

You are given the start and finish times of a DFS (Depth-first search) traversal of the vertices that are available in a rooted tree. Your task is to restore the tree.

Input format

  • First line: Contains an integer $$n$$ that represents the number of vertices of the tree
  • Second line: Contains $$n$$ space-separated integers that denote the start times of the vertices available in a tree
  • Third line: Contains $$n$$ space-separated integers that denote the finish times of the vertices available in a tree

Note:

  • In this problem, the start times are 0-based.
  • It is guaranteed that the input data is consistent.

Output format

Print \(n\) integers. The \(i^{th}\) integer denotes the parent of the \(i^{th}\) vertex or \(0\) if it is the root of the tree.

Note: The vertices of the tree are numbered from 1 to \(n\).

Constraints

\(n \le 300000\)

SAMPLE INPUT
5
2 4 1 0 3
3 5 4 5 4
SAMPLE OUTPUT
3 4 4 0 3 
Explanation

Note that the interval of a vertex is open-ended ( $$[starting_v, finishing_v)$$ ).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?