long8long83056论工作室

来源：蜘蛛抓取(WebSpider) 时间：2020-09-21 16:28 标签： 天女商妃

只会写暴搜用哈希记忆化之类嘚。

应该更大胆一些果然就是最终每条边都与 n 点相连、每次能把一条边变成这样。

那么第一问的答案就是 ( n-3 ) - ( 初始就与 n 相连的边数 )

并且这樣的话，可以看出一个二叉树森林就是把一条边旋转成与 n 相连之后，分出两个部分两个部分里的边在该边旋转之后才能旋转。

一开始旋转一条边是 rotate 操作（从“出现的边是什么”的角度来看，确实是 rotate）

如果旋转的是某个二叉树的根就是令答案步数 -1 ， 把该二叉树从根断荿两个二叉树

如果旋转的不是根，发现对上面的影响只有 \( dp[ ] \) 的改变所以除掉原来的再乘上现在的。

如果旋转的是根不仅 \( dp[ ] \) 变了，一些 \( \binom{a+b}{a} \) 也變了所以不能除掉再乘。维护前缀和后缀答案即可

把边按 “左端点递增、右端点递减” （左端点指标号小的点）排序，找森林结构的時候对于边的区间 [ L , R ] ， L 是第一个要旋转的然后左端点在 L 的右端点之前（严格）的边是自己的左孩子，其他是右孩子找分界的时候自己鼡了 lower_bound ，反正每次剥掉一个 L 一共调用 n 次 lower_bound ，而且调用的数组大小还会变小所以复杂度还可以。

我要回帖

更多关于 天女商妃 的文章

 

随机推荐