P4738 [CERC2017] Cumulative Code

如你所知，树是一个由 $n$ 个节点和 $n - 1$ 条无向边组成的图，其中任意两个节点之间有且仅有一条路径。在标记树中，每个节点都用 $1$ 到 $n$ 之间的不同整数标记。标记树的 Prüfer 码是与该树相关联的唯一序列，通过不断从树中移除节点直到只剩下两个节点来生成。更确切地说，在每一步中，我们移除标号最小的叶子，并将其邻居的标号附加到代码的末尾。回忆一下，叶子是一个只有一个邻居的节点。因此，标记树的 Prüfer 码是一个长度为 $n - 2$ 的整数序列。可以证明，原始树可以很容易地从其 Prüfer 码重建。深度为 $k$ 的完全二叉树，记为 $C_k$，是一个有 $2^k - 1$ 个节点的标记树，其中对于所有 $j < 2^{k-1}$，节点 $j$ 连接到节点 $2j$ 和 $2j + 1$。记 $C_k$ 的 Prüfer 码为 $p_1,p_2,..., p_{2^k-3}$。由于 $C_k$ 的 Prüfer 码可能很长，你不需要输出它。相反，你需要回答关于代码中某些元素和的 $n$ 个问题。每个问题由三个整数组成：$a, d$ 和 $m$。答案是 $C_k$ 的 Prüfer 码元素 $p_a, p_{a+d}, p_{a+2d},..., p_{a+(m-1)d}$ 的和。

第一行包含两个整数 $k$ 和 $q(2 \le k \le 30,1 \le q \le 300)$ —— 完全二叉树的深度和问题的数量。接下来的 $q$ 行中的第 $j$ 行包含第 $j$ 个问题：三个正整数 $a_j, d_j$ 和 $m_j$，使得 $a_j, d_j$ 和 $a_j + (m_j - 1)d_j$ 都最多为 $2^k - 3$。

输出 $q$ 行。第 $j$ 行应包含一个整数 —— 第 $j$ 个问题的答案。

在上面的第一个例子中，当构造 $C_3$ 的 Prüfer 码时，节点按以下顺序被移除：$4, 5, 2, 1, 6$。因此，$C_3$ 的 Prüfer 码是 $2, 2, 1, 3, 3$。 题面翻译由 ChatGPT-4o 提供。