Hello! I have a problem solving problem 150E — Freezing with Style.

It can be solved by Binary Search & Centroid Decomposition & a bit data structure in $$$\mathcal{O}(n\log^2 n)$$$.

But I'm wondering is there an $$$\mathcal{O}(n\log n)$$$ solution?

I suppose Binary Search should be preserved, so here is a $$$\log n$$$. So the problem is : given a tree with it's edge's weights are either $$$1$$$ or $$$-1$$$, determine whether there is a simple path with non-negative total weight and it's length is in $$$[l,r]$$$.

My idea is to use high-low decomposition, you can learn it here (solution of 1009F — Dominant Indices), it looks like DSU on tree but focus on depth of the subtree instead of size. Because this problem also have something to do with depth, I think this method may help.

I can't go any further this way. So I write this blog and hope someone can help me with this problem, thanks!