I hadn't mentioned the conclusion "brute force is $$$O(n\log n)$$$" at first. When i got the dp equation $$$\mathrm{dp}_x=\max(\mathrm{dp}_i,\mathrm{se}_x+1)$$$, where $$$i$$$ is a child of $$$x$$$, and $$$\mathrm{se}_x$$$ is the second maximum $$$\mathrm{dp}_i$$$, my first reaction is that the $$$\mathrm{dp}$$$-s updated in round $$$i$$$ is a path, started from $$$i$$$, and contained in the path $$$i$$$ to root. We can use a Link-Cut Tree (maybe without makeroot(x)? idk) to maintain that. But I don't know to maintain the following:
- $$$\max\mathrm{dp}_i,\mathrm{se}_x$$$
- $$$\mathrm{fr}_x$$$, which means where the $$$\max\mathrm{dp}_i$$$ is from
- $$$\mathrm{stp}_x$$$, which means "when $$$\mathrm{dp}_x$$$ is updated (by 1), where should the update stop
when pushing up and pushing down. After maintaining that, we can simply use a lazy tag to do the dp update. Can anybody help?
Comments (0)
