Problem Link : https://www.codechef.com/STRG2020/problems/PADTREE

Problem : Given a tree, where each node is labelled using lowercase latin character. Find the longest palindromic path. (T <= 15 and N <= 5000)

My Idea : Just like finding a longest palindromic substring, we maintain dp[i][j]. And process this dp from length = 1 to length = 2 and so on... We use LCA to find path length and transition states.

My solution : https://www.codechef.com/viewsolution/40866046 Solution summary : I precompute all N^2 paths and sort them by their path length and process as mentioned above. But I got TLE. Complexity — O(T * N^2 Log(N))

Solution by CoderAnshu : https://www.codechef.com/viewsolution/40861653 Solution summary : Uses similar approach but instead of precomputing paths, he expands set from length 1 by keeping queue. Can you please explain the time complexity? And perhaps where I might be going wrong?

Can someone please help with the above problem?