转换构成树的条件：

• 不存在环。于是不可以存在三条线段共点的情况，每个点最多被两个线段覆盖。
• 只有一个连通块。所有线段覆盖的点需要是连续的。

我们从左往右处理这些线段，按照左端点 的大小排序。定义状态 表示处理到第 条线段，所选取的线段的所有右端点 中最大的是 ，次大值是 的方案数。

考虑选择加入第 条线段 时的转移。为了防止破坏树的性质，显然需要有 。得到转移：

• 。

然后优化：

• 这一维显然可以滚掉。
• 注意到 不会进入新的状态中，于是可以用前缀和优化掉。

时间复杂度：。

空间复杂度：。