2018-4-13模拟赛:D

2018-4-13模拟赛:D
假如可以快速预处理出所有点的最远点那么就可以O(1)回答了。
有一个经典的树形dp套路就是dfs两遍,第一次维护子树内的信息,第二次求出答案(包括子树外)。
具体的实现/理解方法很多。对这题而言,在第一次dfs的时候求出子树内的最长链和次长链(这两条链需要从不同的儿子转移过来)。
然后再做一次dfs,这次要用fa更新儿子,假如最长链就是由这个点转移过来的话就用次长链更新,否则就用最长链。
因为上一问太水,所以强行套了个单调队列……
求极值不超过m的最长子串应该是单调队列的经典操作。
考虑双指针,因为r右移时l也是单调右移的,所以用两个单调队列得到l即可,一个单调上升,一个下降。
假如您nlogn过了那我也没办法……

发表评论

电子邮件地址不会被公开。 必填项已用*标注