Given the employee\'s traversal of the park, and the exhibits that the visitors want to visit determine

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Story

Your park has a new layout. The park is modeled as a collection of exhibits (including the entrance of the park) each with their own unique ID. There are also paths in your park. Each path connects a pair of exhibits. Additionally, between each pair of exhibits there is exactly 1 sequence of unique paths that connects. One aspect of the park that draws in a lot of guests are the monkeys that hang around each exhibit (including the entrance of the park).

Guests that visit your park love to see a lot of monkeys. However, the guests are very busy, so they typically have time to walk from the entrance to one particular exhibit, then walk back to the entrance to leave. They don’t visit any more exhibits than necessary. You were going to give the visitors a map so that they could plan out the visits that would enable them to visit the most monkeys, but someone swiped your reference map. Now you want to settle for telling the guests how many distinct monkeys they will see in their visit to your park.

Luckily, you have a dedicated employee that walked the entire park to give you a report of the existing pathways and the monkeys at each location. The employee started at the entrance and crossed all pathways exactly twice. The first time the employee reached a location they wrote down a unique integer ID for the location and the number of monkeys they saw. Everytime they used a pathway a second time they reached an exhibit they had already seen, so they noted that the exhibit had already been recorded in their notes. The employee may have visited an exhibit multiple times.

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 exhibits in 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.

 

Attachments:

Expert's Answer

493 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of