I was trying to solve this problem in the contest today, this was some kind of DP on trees which can be solved using re-rooting type DP but I got another idea and I tried to implement it but unfortunately got TLE. I would like to ask the CODECHEF community to see through it once and see if anyone can help me with the time complexity of my solution.

@ssjgz

Looks O(N^2) to me: consider the case where N is large and vertices 2,3,\dots N-1 are connected to vertex 1.

1 Like