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.

I was solving the problem 607A - Chain Reaction and got WA on test case 11. Here's my submission 82317236. dp[i] is basically the number of destroyed beacons if we consider the coordinates [0,i]. numBeacons[i] is the total number of beacons again in [0,i]. Please help me where I am wrong. Have been stuck in this problem for a while now.