I was solving this problem 219D - Choosing Capital for Treeland. Here's my submission 83899446 which resulted in TLE. My logic is pretty straight forward. dp[par][u] is basically the number of inversions required in the subtree having u as the root after we cut off the edge between u and par. Since N can be upto 1e5, I used an array of maps instead of a 2-D matrix.
Now if we analyze the number of entries in this dp data-structure, it would be of the order of the number of edges i.e. N-1 (actually two times it as for every two neighboring vertices, there can be two entries).
Since the time complexity of any algorithm depends upon the number of subproblems being solved, shouldn't it run in O(N)? Please correct me if I am wrong.
Someone please help me out here.
Notice that the graph you're failing on is a star, specifically one that's centered at the vertex $$$200000$$$. So your algorithm is roughly: for i from $$$1$$$ to $$$199999$$$, enter
dfs(i, 200000), visit all the $$$199999$$$ neighbors of $$$200000$$$, and then fill your dp state for $$$dp(i, 200000)$$$.So your complexity analysis is wrong because it could take up to $$$O(n)$$$ to fill each dp state, and there are $$$O(n)$$$ of them.
Ok so if I understood you right, there would be O(N2)
dfs(par,u)calls in worst case although the number of entries in dp could still be of the order of N.I suppose so, yes, and you'll end up revisiting already-computed states a lot.
So my precomputations won't save me from getting TLE :(
Anyways, thank you for the clarification buddy.