P17868 [FJCPC 2026] 胖虎与线段树

在糕棠国，苔山皇帝胖虎正为了《大学物理》的期末考试焦头烂额。为了高效备考，他决定**更欣**一份基于"线段树"的复习大纲。 遗憾的是，在划分复习区间时，他记错了物理公式的边界条件。于是，这份复习大纲不再从中间平分知识点，而是每个大章节都可能被随机划分成任意的两部分。 尽管如此，这依然是一棵合法的二叉线段树结构： - 根节点表示全部知识点的总区间 $[1, n]$； - 每个叶子节点表示某个单一知识点的区间 $[i, i]$； - 每个非叶子节点表示一个包含多个连续知识点的区间 $[l, r]$，并被划分成两个子区间 $[l, x]$ 和 $[x + 1, r]$，其中 $l \leq x < r$。 现在，给你这棵"复习大纲树"上所有节点对应的区间。请注意，输入中只给出每个节点代表的区间 $[l, r]$，并不直接给出具体的划分点 $x$。 对于某次测验的考察范围 $[l, r]$，我们定义胖虎的复习代价 $f(l, r)$ 为： 从这棵大纲树的若干个节点中选出一些两两不相交的区间，使它们的并集恰好等于测验范围 $[l, r]$，所需节点数量的最小值。 （换言之，就像查询普通线段树时会把目标区间拆分成若干个节点，这里的 $f(l, r)$ 就是能够精准覆盖 $[l, r]$ 的最少节点数。） 当期末考试出分之后，春老师在群里微笑着对大家说： :::align{center} **同学们好，我们的期末成绩设置了达标线。** ::: 很遗憾，胖虎并没有通过达标线。看在胖虎帮老师安装 Arch Linux 系统的份上，春老师给胖虎一次复活考核：处理 $n$ 个物理实验样本（保证 $n$ 为偶数），编号依次为 $1,2,\cdots,n$。春老师要求将它们两两配对进行对照实验。 如果将样本 $a$ 和 $b$ 配成一对，设 $l = \min (a, b)$，$r = \max (a, b)$，为了弄清这组对照实验背后的物理原理，胖虎必须查阅大纲中对应范围的知识，因此这一对产生的复习代价即为 $f(l, r)$。 为了能打赢春老师设置的复活赛，胖虎需要将这 $n$ 个样本划分成 $\frac{n}{2}$ 对，使得总复习代价最小，并输出一组最优的实验配对方案。如果有多组最优方案，输出任意一组即可。 糕棠虎忙着去苔冬找外国语搭子备考雅思了，于是把问题抛给了你。

输入包含多组测试数据。 第一行包含一个整数 $T$（$1 \leq T$），表示测试数据组数。 对于每组测试数据： - 第一行包含一个偶数 $n$（$2 \leq n \leq 5000$）。 - 接下来 $2n - 1$ 行，每行包含两个整数 $l, r$（$1 \leq l \leq r \leq n$），表示线段树中的一个节点区间 $[l, r]$。 输入保证这 $2n - 1$ 个区间恰好是一棵合法二叉线段树的所有节点区间。 此外，保证所有测试数据的 $\sum n \leq 5000$。

对于每组测试数据： - 第一行输出一个整数，表示最小总代价。 - 接下来输出 $\frac{n}{2}$ 行，每行输出两个不同的整数 $a,b$，表示将 $a$ 与 $b$ 配成一对。 所有输出的整数 $1,2,\cdots,n$ 必须恰好各出现一次。 若存在多组最优方案，输出任意一组即可。

:::align{center}  ::: 这组输出对应的配对为： $$ [1,8], [2,3], [4,5], [6,7].$$ 其中： $$[1,8]\in S,\qquad [2,3]\in S,\qquad [4,5]\in S.$$ 所以： $$f(1,8) = 1,\qquad f(2,3) = 1,\qquad f(4,5) = 1.$$ 但是 $[6,7]$ 本身不是树上的节点。它需要拆成两个单点： $$[6,7] = [6,6]\cup [7,7].$$ 因此： $$f(6,7) = 2.$$ 总代价为： $$1 + 1 + 1 + 2 = 5.$$