Hi, I'm trying to solve Gym 102263E Longest Path Problem and my code can be found here. My strategy is to think of each edge as a bridge that splits the tree in 2 subtrees, and the subtree I'm interested in depends on which direction (forward or backward) I'm considering. So, given edge e=(u,v), if I consider the forward direction then I'm interested in the subtree that has v as root (and u is the parent of v), whereas if I consider the backward direction then I'm interested in the subtree that has u as root (and v is the parent of u). Thus, I can use dynamic programming to compute many things for the subtree forward and the subtree backward defined by each edge, the signature of the DP is basically DP(edge, direction) where edge $$$\in [1,N-1]$$$ and direction $$$\in$$$ { forward, backward }. Using this strategy I can recursively compute the diameter, the end nodes of a diameter, the maximum depth and the deepest leaf for both subtrees (forward and backward) associated to each edge in O(N). Once I have that, then the answer for each edge is the maximum between the diameter forward, the diameter backward and the longest path that we obtain by connecting the center of the subtree backward and the center of the subtree forward with the current edge. To find the center of each subtree, I use binary search between the end nodes of a diameter (found in the DP previously explained) using LCA with binary lifting method in the predicate.

I debugged my solution a lot and it's working with the example and I created some additional examples by hand and it's working with them too. However I'm getting wrong answer on test 3. I would really appreciate if somebody could help me out by providing some tricky test cases to test my solution with. Unfortunately gym doesn't show the test cases so I had to create test cases myself but my solution seems to work all the time. Maybe there is something wrong in my strategy somewhere, some tricky corner cases which I'm overlooking.

Thank you very much in advance.

Update: I debugged my solution a little more and realized I had a bug in a function that finds the k-th node in the path from u to v, I fixed that bug but now I'm getting TLE on test case 60 :(, any tips on how to optimize my code even more? You can find my latest code here