adityaaaaaaaaaaaaaaa's blog

Why is this TLE (dp on trees)?
By adityaaaaaaaaaaaaaaa, history, 6 years ago, In English

55968842 The question (337D - Книга Зла) is on dp on trees. I cant find out why this code is TLEing. Any help would be appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 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).

→ Reply
»
6 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).

→ Reply
»
6 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.

→ Reply