Problemas De Programacion

acm

International Collegiate Programming Contest

2010

event sponsor

ACM International Collegiate Programming Contest 2010
Latin American Regional Contests
October 22nd-23rd, 2010

Contest Session

This problem set contains 11 problems; pages are numbered from 1 to 15.

This problem set is used in simultaneous contests hosted in the following countries: • Argentina • Bolivia •Brazil • Chile • Colombia • Cuba • Peru • Mexico • Venezuela
v1.0

General Information
Unless otherwise stated, the following conditions hold for all problems.

Input
1. The input must be read from standard input. 2. The input contains several test cases. Each test case is described using a number of lines that depends on the problem. 3. When a line of data contains several values, theyare separated by single spaces. No other spaces appear in the input. There are no empty lines. 4. Every line, including the last one, has the usual end-of-line mark. 5. The end of input is indicated with a line containing certain values that depend on the problem. This line should not be processed as a test case.

Output
1. The output must be written to standard output. 2. The result of each testcase must appear in the output using a number of lines that depends on the problem. 3. When a line of results contains several values, they must be separated by single spaces. No other spaces should appear in the output. There should be no empty lines. 4. Every line, including the last one, must have the usual end-of-line mark. 5. No special mark should be written to indicate the end of output.ACM ICPC2010 – Latin American Regional

1

Problem A
Ants Colony
Problem code name: ants A group of ants is really proud because they built a magnificent and large colony. However, the enormous size has become a problem, because many ants do not know the path between some parts of the colony. They desperately need your help! The colony of ants was made as a series of N anthills, connectedby tunnels. The ants, obsessive as they are, numbered the anthills sequentially as they built them. The first anthill, numbered 0, did not require any tunnel, but for each of the subsequent anthills, 1 through N − 1, the ants also built a single tunnel that connected the new anthill to one of the existing anthills. Of course, this tunnel was enough to allow any ant to go to any previously builtanthill, possibly passing through other anthills in its path, so they did not bother making extra tunnels and continued building more anthills. Your job is, given the structure of the colony and a set of queries, calculate for each query the shortest path between pairs of anthills. The length of a path is the sum of the lengths of all tunnels that need to be traveled.

Input
Each test case isgiven using several lines. The first line contains an integer N representing the number of anthills in the colony (2 ≤ N ≤ 105 ). Each of the next N − 1 lines contains two integers that describe a tunnel. Line i, for 1 ≤ i ≤ N − 1, contains Ai and Li , indicating that anthill i was connected directly to anthill Ai with a tunnel of length Li (0 ≤ Ai ≤ i − 1 and 1 ≤ Li ≤ 109 ). The next line contains aninteger Q representing the number of queries that follow (1 ≤ Q ≤ 105 ). Each of the next Q lines describes a query and contains two distinct integers S and T (0 ≤ S, T ≤ N − 1), representing respectively the source and target anthills. The last test case is followed by a line containing one zero.

Output
For each test case output a single line with Q integers, each of them being the length ofa shortest path between the pair of anthills of a query. Write the results for each query in the same order that the queries were given in the input.

ACM ICPC2010 – Latin American Regional

2

Sample input 6 0 1 1 0 4 4 2 5 1 0 2 0 2 1 0 6 0 1 2 3 4 1 5 0 8 7 9 3 2 3 2 4 3 1 0 1 1000000000 1000000000 1000000000 1000000000 1000000000 0

Output for the sample input 16 20 11 17 1 1...