Sample Input 4 1 10 2 13 4 25 -1 36 -1 -1 3 4 3 2 Sample Output 48 29 23
How would I code this in C using trees?
Problem
Given the employee's traversal of the park, and the exhibits that the visitors want to visit determine how
many unique monkeys the visitor will see on their way from the entrance to the exhibit and then back.
Input
Input will begin with a line containing 1 integer, n (1 ≤ n ≤ 200,000), representing the number of exhibitsin the park (including the entrance). The following line contains 2 integers, i and m (i = 1; 1 ≤ m ≤ 5,000), representing the ID of the entrance and the number of monkeys at the entrance. Each of the following 2n - 2 lines will contain a path description recorded by our employee. If this is the first time the employee used the path, then the line will contain two integers, i and m (2 ≤ i ≤ n; 1 ≤ m ≤ 5,000), representing the ID of the destination exhibit and the monkeys at the destination exhibit respectively. If this is the second time the path is used, then the line will contain the integer -1 instead, since the ID and number of monkeys were already recorded. You can assume that the monkeys don’t move between exhibits. The following line contains a single integer, v (1 ≤ v ≤ 500,000), representing the number of visitors to the park. The following v lines will each contain a single integer, e (1 ≤ e ≤ n), representing the ID of the exhibit that the guest is going to visit.
Output
Output should contain v lines. Each line will contain a corresponding integer representing the number of
unique monkeys seen in the corresponding visitor’s park visit. The order of the output should correspond
to the order of the input.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 5 images