adityaaaaaaaaaaaaaaa's blog

By adityaaaaaaaaaaaaaaa, history, 5 years ago, In English

55968842 The question (337D - Book of Evil) is on dp on trees. I cant find out why this code is TLEing. Any help would be appreciated.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adityaaaaaaaaaaaaaaa (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adityaaaaaaaaaaaaaaa (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your dfs2 method is $$$N^2$$$ complexity. Think about a tree which is one root node connected to 100k leaf nodes. Then for each leaf node you loop over the parent's children again, which is 100k. So that's 100k^2.