怎么这题还要还原方案的。 /fn

首先，看到区间之间包含或不交，考虑按照包含关系建树，每个区间的父亲是包含它的长度最小的区间。建完树后将一个点的儿子按位置关系排序。

然后在树上考虑 DP。设一个点 共有 个儿子，那么其会将 分为 段。考虑属于 的答案怎么填。一共就两种情况：

1. 其可以完全被某个儿子包含，相当于在这个儿子处 DP 时要多处理一条线段。
2. 也可以跨过这 段中的一段，并可能与某个儿子的后半部分拼接，和另一个儿子的前半部分拼接。

那么 DP 状态就可以设出来了。设 表示在 子树中，填 条线段，是否有一条线段的左端点在 外，是否有一条线段的右端点在 外的最优答案。（ 表示 的子树大小， 其实就表示从祖先处传过来 条线段，对应情况 1）注意，对于左端点在 左边的那条线段，我们先不将其左端点对答案的贡献计入 DP 值，这条线段也不计入 中。等到某次 DP 时，这个左端点被确定了，再将其算进来。

考虑如何进行转移：设 表示在点 的前 个儿子及其中间的空段中，多填入 条线段 （ 的意义类似上面），前后是否有未完全确定的线段。

设 表示 的第 个儿子， 的转移是简洁的： 第二个转移表示在 和 之间的空档填了一条线段。此时 中记录了该线段左端点的贡献， 中记录了该线段右端点的贡献，直接相加就可以将这一条线段的贡献算入 DP 值中。

设 表示点 的最后一个儿子。那么 也可以从 转移过来： 第一条式子其实没有新增任何线段，但因为 本身就要求填一条线段，所以 “多填的线段数”就少了一条。第二条式子中，如果 ，那么相当于闭合一条在 中还未完全确定的线段并加上贡献。第三条式子同理。

这个 DP 乍一看是 的，毕竟我们没有说明 的规模。但事实上，一个有 个儿子的点最多将自己划分为 段，所以 子树最多被划分为 段。所以，如果线段条数多于 ，那 子树中的所有位置都可以被答案线段覆盖。所以只需记录 的 DP 值即可得到正确答案。

接下来考虑怎么还原方案。

首先从 开始，考虑回溯转移路径，这个可以用递归函数实现。然后分几种情况讨论答案线段的位置。