Like this problem: https://codeforces.net/problemset/problem/161/D but you save the shortest path with a path length i call it dp[i]. Assuming that you are considering centroid c, after going through a tree branch, you save the dp[i] as the shortest path of length i from c every time you move to a new branch, the result will update again as min(ans , dp[i]+dp[k-i]) with the condition dp[i]!=-1 && dp[k-i]!=-1. Because k is quite large, when you finish browsing 1 centroid, you will only update the dp you just reviewed. sorry my english is very bad My code for this problem: https://ideone.com/VOmd3A