I was trying solve this problem and I've thought of O(T * N) solution that uses Tarjan+DP. I thought O(T * N2) wouldn't work because . But solutions on this blog and this blog seem to me as O(T * N2).
How do they get accepted? Is it just because of weak test cases, or is there something else I'm missing here?