### terserah's blog

By terserah, history, 3 years ago,

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?

• +8

 » 3 years ago, # |   +6 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.
•  » » 3 years ago, # ^ |   0 Thanks for your hint. I'll try it again.
 » 5 weeks ago, # |   0 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.