All Tracks Data Structures Trees Problem

Employee Complaints Management

Medium-Hard, approved


ABC company is building an Employee Complaint Management (ECM) system. Currently the company has $$N$$ employees. Each employee is identified with his/her employee ID which is an integer between $$1$$ to $$N$$. Each employee has exactly one boss, except the employee with employee ID $$1$$, the owner of the company. The structure is hierarchical i.e. an employee will be a boss of all the subordinates of his/her subordinates. Currently the ECM has following two features:

  1. Help Employees make complaints. Any employee $$A$$ can complain about any other employee $$B$$ to any of their common bosses.
  2. Help Employees track the status of their complaints.

Now they want to add one more feature. They want to add a recommendation system. If any employee wants to make a complaint against any other employee, it will recommend them the Employee ID of their common boss having the maximum Justice Factor. They calculate the Justice Factor for employees using ML Techniques. They'll provide you the current value of Justice Factor for all the employees, they just want you to write an optimal program such that given a lots of queries of type $$x \space y$$, meaning that employee ID $$x$$ wants to complain about employee ID $$y$$, it returns the employee ID of their common bosses having the maximum Justice Factor.

Input Format:
First line consists of a single integer denoting $$N$$.
Second line consists of $$N$$ space separated integers where the $$i^{th}(1 \le i \le N)$$ integer denotes the Justice Factor of employee having ID $$i$$.
Third line consists of $$N-1$$ space separated integers denoting the boss's employee ID of all employees having ID between $$2$$ to $$N$$.
Fourth line consists of a single integer $$Q$$, denoting the number of queries.
Following $$Q$$ lines consists of two space separated integers $$x \space y$$ denoting that employee $$x$$ wants to complain about employee $$y$$.

Output Format:
For each query, print the ID of the common boss of $$x$$ and $$y$$ having maximum Justice Factor in a new line.

$$1 \le N, Q \le 10^5$$
$$1 \le X, Y \le N$$

Note: It is ensured that no two employees have same value of the Justice Factor, and that no employee will ever want to make a complaint about one of their bosses.

1 2 3 4 5
1 1 2 2
4 5
5 3

$$4$$ and $$5$$ have two common bosses, having ID $$1$$ and $$2$$, out of those $$2$$ is having the maximum Justice Factor.
$$5$$ and $$3$$ have only one common boss i.e. $$1$$, so that is the answer.

Time Limit: 1.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


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

{Hack a Heart}()=>love for<code/>;</code>for love;

View All Notifications