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.
