暑期总结1

第一周学了笛卡尔树和基环树。

笛卡尔树就是 Treap青春版(?)，满足以下性质：

• 是一颗 BST。
• 中序遍历 存在单调性。

建树可以 $\Theta(n)$ 完成，方法是用单调栈维护当前节点的有儿子链。

放一张图 (来自 oi wiki )：

然后就是各种 $DP$。。。

---

---

---

基环树就是在一颗树上加一条边。

不难发现，这东西有一个环。

所以题目大概可以拆成 树+环 的形式。

树上要 $DP$ ，环上要数据结构，找环要 tarjan，代码可能 3000+。

评价：

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$口胡一时爽，代码火葬场。

后记：int函数没返回值导致了