Help required in DDQUERY

I had done 50 points during the contest using BFS and keeping track of the distance but it gave TLE for the last 3 test cases. Any idea on how to solve it for 100 points?