楼主试图挑战一下20年D1T2,口胡2h搞出了的状态与方程与第一篇题解基本一致,不同之处仅有两处:状态第二维的定义是“此时下端点在某结点子树内的所有路径中,全部的满足上端点深度不超过 x 的路径的要求被满足”,这一点和第一篇题解的状态应该是等价的;而另一初不同在于初始状态,这也是楼主一直以来的弱项:想出了状态干出了方程被初始状态给创死。
和第一篇题解与楼主思路基本一致的题解的初始状态都是对于每条规定路径的下端点,第二维为所有以它为下端点的所有路径中上端点深度最大的数值对应的状态赋初值 1 ,而楼主这边的初始状态是对于每个路径的下端点,第二维在【最浅上端点深度+1,最深上端点深度】(用katex不好写先不用了)这个闭区间内的所有状态赋初值1。
由于能去机房那一天楼主线段树调炸了,没能编程实现测试,现在也没有条件测试(帖子用PAD发的),请教各位神犇楼主这个第二维状态是否正确以及原因(比如在后续转移之后没有差别之类),与大部分人的区别在哪里。若可以的话,楼主还想请教一下初始状态总想不出来的问题怎么解决。
若能够帮助,本人不胜感激。