Limits
3s, 1.0 GB

Have you ever heard of The Atlantis City? It’s a Greek mythological city. Its existence doesn’t matter to us anymore. But last night I had a nightmare. Poseidon, The King of Great Atlantis City, came to me and gave me a problem. Now you must write a program that can solve the Poseidon problem.

Atlantis City consists of N number of forts. They are connected by N-1 number of roads. Fort 1 is The Palace of King Poseidon. There is a soldier in every fort. For traveling each road, a transport cost has to be paid. This payment has to be made by coins. But there’s a strange rule in Atlantis city. Every fort can keep only one type of coin. Now Poseidon wants to know if fort f have p valued coin, what is the nearest fort from the palace where a soldier of fort f can reach.

Now for each query, your program should receive two integers f, p and print a fort number v which is the nearest from The Palace and can travel from f to v using only p valued coin. You can assume that there are unlimited numbers of p valued coin in fort f.

Poseidon said that he would come tonight in every contestant’s dream and ask for a program which can answer the query. So Hurry Up!

First Line consists of an integer **T** (1 ≤ T ≤ 5), number of test cases.

Each test case starts with an integer **N** (2 ≤ N ≤ 100000), the number of forts in Atlantis city. Next N-1 lines, each line contains three integers **u**, **v** (1 ≤ u, v, f ≤ N), **w** (1 ≤ w ≤ 10000000), where there is a road in u and v; w is the traveling cost of this road.

Then there’s one integer **q** (2 ≤ q ≤ 100000), number of queries. Next q lines each contains two integer **f** (1 ≤ f ≤ N), **p** (1 ≤ p ≤ 10000000) where f is the fort number and p is the value of the coin.

At first print case number. For each query, you should print a line containing fort number which is the nearest fort from The Palace and can reach from f using p valued coin. For detailed output format, please see sample output.

Input | Output |
---|---|

1 4 1 2 10 1 3 7 4 3 14 3 2 5 4 7 4 10 | Case 1: 1 1 4 |

Input | Output |
---|---|

1 5 1 2 2 1 3 7 3 4 10 5 4 15 2 5 5 2 1 | Case 1: 3 1 |

Login to submit.

85%
Solution Ratio

IOI_StfuFfsEarliest,

Takik_Fastest, 0.0s

experimenterLightest, 25 MB

IOI_StfuFfsShortest, 1178B

Toph uses cookies. By continuing you agree to our Cookie Policy.