NTICKETS - Nlogonian Tickets

no tags 

You live in Nlogonia, a country that has N cities connected by some bidirectional roads (as usual). In Nlogonia, there is exactly one path between any pair of cities.

You can't use the roads during your travels for free. There is an officer at each road that will let you use it only if you show him a certain number of tickets. If you don't have the required amount of tickets, you just can't use that road.

The officer will not keep the tickets, though. You need to show the tickets to him, but you can keep them after that. This indicates that you can use the same ticket in more than one road, if you want to.

You are given a description of the road system of Nlogonia and a number of queries. For each query, find the minimum number of tickets you must have to go from a city A to a city B. Consider that city A is the only place where you can buy tickets, so you must be holding all the tickets you will need during the travel before leaving city A.


Each test case starts with a line containing the integer N (2 ≤ N ≤ 105), the number of cities in Nlogonia. The cities are numbered from 1 to N.

Each of the next N-1 lines contains the description of a road, A B T (1 ≤ A, B ≤ N, A ≠ B, T ≤ 109), indicating that there's a road between the cities A and B, and you must show T tickets to use it. It's guaranteed that no pair of cities will appear more than once in the input.

The next line contains the integer Q (1 ≤ Q ≤ 5×105), the number of queries. Each of the next Q lines contains two city numbers A B (1 ≤ A, B ≤ N, A ≠ B).

The last test case is followed by a line containing the number 0.


For each query A B, print the minimum number of tickets needed during the travel from city A to city B. Print a blank line after each test case.


1 2 1
1 3 5
3 4 3
3 5 8
1 6 2
2 6
5 2
4 6


hide comments
fuadul_hasan: 2022-06-23 19:10:55

why I am getting TLE please anyone help me

[Simes]: Please use the forum for this.

Last edit: 2022-06-24 07:44:05
abhinav_jain02: 2019-05-17 14:52:06

Use fast i/o and LCA
Also,note that each test case gives a separate graph with its own set of queries

Last edit: 2019-05-17 14:52:57
joe85123: 2019-03-23 17:20:11

time limit is really strict....
added a lot of optimization to get AC (using buffer for input, etc)

yashkodesia: 2018-12-17 13:06:14

AC in 2nd go due to harsh time limits! :(

sherlock11: 2018-06-27 21:21:56

after so much of effort finally AC:)...............

narek: 2018-06-19 02:32:10

tle :( also using LCA
Accepted :D time limit is a little bit too harsh

Last edit: 2018-06-19 02:34:55
humbletheif: 2018-06-16 23:26:43

I used lca and getting correct output for the above test case...but WA when submitting the solution..Am i missing something important??
edit:got AC...don't forget to clear vectors before each test case.

Last edit: 2018-06-16 23:42:43

Added by:Ricardo Oliveira [UFPR]
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFPR/Own problem