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
