P14194 [ICPC 2024 Hangzhou R] Heavy-light Decomposition

$\textit{重链剖分}$（HLD）是一种应用于树结构的高效查询顶点链的技巧。我们首先来回顾一下 HLD 的定义，以防你忘记了。 给定一棵有 $n$ 个顶点的有根树，节点编号从 $1$ 到 $n$。 你需要将每个非根节点分类为重节点或轻节点。 每个非叶子节点恰好有一个子节点被标记为重节点，其余的子节点被标记为轻节点。 对于任意非根节点 $v$，设 $u$ 为其父节点。节点 $v$ 只有在其子树大小在 $u$ 的所有子节点中最大时才可以被分类为重节点。更正式地，设以 $v$ 为根的子树大小为 $s_v$，$\text{ch}(u)$ 表示 $u$ 的所有子节点的集合。那么，仅当 $s_v \geq s_w$ 对所有 $w \in \text{ch}(u)$ 成立时，$v$ 才能被标记为重节点。注意，可能有多个 $u$ 的子节点满足这一条件，此时你需要从中选择一个作为重节点，其余的为轻节点。 在上述分类后，可以把树的所有节点划分为若干条不重叠的重链，每个节点属于且只属于一条重链。重链是满足以下所有限制的顶点序列 $x_1, x_2, \ldots, x_k$： - $x_1$ 要么是根节点，要么是轻节点。 - 对于所有 $2 \leq i \leq k$，$x_i$ 是 $x_{i-1}$ 的子节点且为重节点。 - $x_k$ 是叶子节点。 :::align{center}  HLD 示例。重链用红色实线标记。 ::: 例如，上图展示了一个包含 $12$ 个顶点的树的合法 HLD，其中重链为 $[1, 2, 3, 4, 5]$、$[9, 10, 11]$、$[7, 8]$、$[6]$ 和 $[12]$。 Pig100Ton 是 Pigeland 的一名经验丰富的竞赛选手。他想知道，是否可以通过 HLD 得到的若干重链，唯一还原出原来的树结构。具体来说，他会给你原树的顶点数 $n$ 以及 $k$ 条重链说明。 第 $i$ 条重链由两个整数 $l_i$ 和 $r_i$ 描述，表示该重链为 $l_i, l_i + 1, \ldots, r_i$。 你的任务是，构造出满足以下条件的树，或者告知 Pig100Ton 不可能： - 这是一棵包含 $n$ 个顶点、编号为 $1$ 到 $n$ 的有根树。 - Pig100Ton 给出的 $k$ 条链应当对应该树的一个有效 HLD。有效 HLD 指的是一种合法划分每个非根节点为重节点或轻节点的方式，然后能将树分解为若干条不重叠的重链。

输入包含多组测试数据。第一行为一个整数 $T$（$1 \le T \le 10^5$），表示测试用例的数量。对于每组测试数据： 第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$，$1 \leq k \leq n$），表示树的节点数以及 HLD 后重链的数量。 接下来的 $k$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 条重链为 $l_i, l_i + 1, \ldots, r_i$。 保证每个节点恰好属于一条给定的重链。所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例： 如果可以构造出这样的树，则输出一行包含 $n$ 个整数 $p_1, p_2, \cdots, p_n$，以空格分隔，其中 $p_i$ 表示节点 $i$ 的父节点。如果 $p_i = 0$，表示节点 $i$ 是根节点。如果存在多组方案，输出任意一组即可。 如果无法构造，则输出一行 $\texttt{IMPOSSIBLE}$。

对于第一个测试用例，样例输出正对应描述部分中的树。 由 ChatGPT 5 翻译