Mancunian And Colored Tree - (Hackerearth Tree Problem)



The problem is simple:

Each node is assigned a color. For each node, we are being asked to find its closest ancestor having the same color.

Why would my O(n) solution go TLE? In comments I’m seeing O(n^2) recursive solutions being accepted. Any kind of help would be appreciated. To be clear, from test 11 and onwards, the test size goes beyond 70,000.