terserah's blog

SPOJ — MAXCHILDSUM
By terserah, history, 7 years ago, In English

Hello, can anybody give me hints for this problem? I think heavy light decomposition could handle the type-1 query, but how about the type-2 query?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

My (author's) solution uses the fact that there are not many nodes having many children and nodes with not so many children are easy to handle.

Of course, as an author I don't want to reveal the full solution but I think this hint is enough for you to get it. I am happy to see many different approaches that didn't occur to me, including a good portion of HLD solutions.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved this using this technique e.e in $$$O(n \log^2 n)$$$, I can optimize it to $$$O(n \log n)$$$ using this blog.

→ Reply