Distance between shelters
Statement
A mountain has N shelters, and the shelters are numbered 1 through N. There are N-1 trails between the shelters, and each trail joins two shelters directly and has a set length. Following these N-1 trails you can get from any shelter to any other shelter, and there is always only one path joining two shelters.
The management office gets M queries from hikers. Each query names two shelters and asks for the distance from the first shelter to the second one along the trails. The distance is the sum of the lengths of the trails walked. Since there is only one path joining two shelters, the distance is settled as a single value. A query can also name the same shelter twice, and in that case there is nowhere to walk, so the distance is 0.
Write a program that, given the trails and the M queries, works out the distance for each query in order.
For example, suppose there are N=4 shelters and 3 trails laid out as in the table below.
| Trail number | 1 | 2 | 3 |
|---|---|---|---|
| Shelter on one side | 2 | 4 | 1 |
| Shelter on the other side | 1 | 3 | 4 |
| Length of the trail | 2 | 2 | 3 |
Now suppose M=2 queries came in, in order. The first query asks for the distance from shelter 1 to shelter 3. Getting from shelter 1 to shelter 3 means going from 1 to 4 and then from 4 to 3, so the distance is 3 + 2 = 5. The second query asks for the distance from shelter 2 to shelter 4. Getting from shelter 2 to shelter 4 means going from 2 to 1 and then from 1 to 4, so the distance is 2 + 3 = 5.
| Query number | 1 | 2 |
|---|---|---|
| Starting shelter | 1 | 2 |
| Arriving shelter | 3 | 4 |
| Distance | 5 | 5 |
So the answers in this example are 5 and 5, in that order. The two queries came out as the same value, but the trails walked are different.
Queries whose starting shelter and arriving shelter are the same come in as well. For example, a query asking for the distance from shelter 1 to shelter 1 has the answer 0, since there is nowhere to walk.
Input and Output Examples
Example 1
Input
4 2 2 1 2 4 3 2 1 4 3 1 3 2 4
Output
5 5
Example 2
Input
3 3 1 2 131 2 3 289 3 1 1 3 3 3
Output
420 420 0
Example 3
Input
3 1 1 2 789 1 3 785 3 3
Output
0
Input
First the number of shelters N and the number of queries M are given on the first line, separated by a space. N is a natural number from 2 to 1,000, and M is a natural number from 1 to 1,000.
Next the information on each trail is given over N-1 lines. Each line holds the numbers of the two shelters the trail joins and the length of the trail, separated by spaces. The two numbers are natural numbers from 1 to N, and the length of the trail is a natural number from 1 to 1,000.
Next the information on each query is given over M lines. Each line holds the number of the starting shelter and the number of the arriving shelter, separated by a space, and both numbers are natural numbers from 1 to N.
Output
For the M queries, print the distance between the two shelters along the trails, one per line, in order. Keep the order in which the queries came in. For a query that names the same shelter twice, print 0.
Requirements
- There are N-1 trails, and these trails alone get you from any shelter to any other shelter
- There is only one path joining two shelters
- The distance is the sum of the lengths of the trails walked
- Print the answer for each query, one per line
- The answer for a query that names the same shelter twice is 0
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 15 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.
3 1 1 2 789 1 3 785 3 3
0
3 3 1 2 131 2 3 289 3 1 1 3 3 3
420 420 0
4 2 2 1 2 4 3 2 1 4 3 1 3 2 4
5 5
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
Nobody yet. You could be the first.