Problem description : https://www.urionlinejudge.com.br/judge/en/problems/view/1476

My code : http://pastebin.com/9X29pLcf

I have been trying to solve this problem for a while. I'm not sure if my idea is correct (LCA with dfs preprocess and segment tree queries), but i think it is. I have found a test case that breaks my program, and i know the reason my program fails in this case, but i don't know how to fix it because i don't have a lot of experience with LCA algorithm.

Explanation : i want to determine the bottleneck edge in the path from vertex A to vertex B. The query in my segment tree returns the smallest weight, but it considers all vertexes that were visited between A and B in the dfs, and some of these vertexes are not included in the path from A to B.

Any help will be much appreciated! Thanks in advance.

Bad test case:

6 5 8

4 1 39

2 4 80

6 1 29

4 5 35

3 1 21

4 2

4 6

5 1

5 4

4 2

3 4

3 4

5 1

Expected output:

80

29

35

35

80

21

21

35

My program output:

39

29

35

35

39

21

21

35