P15763 [JAG 2025 Summer Camp #1] Billion Tree

这是一道交互题。 交互过程包含两个阶段。 ### 阶段 1 你必须首先选择一个整数 $N$（$2 \leq N \leq 65$）。然后你必须输出所选的 $N$ 以及一棵满足以下条件的 $N$ 个顶点的树 $T$： - 顶点编号为 $1, 2, \ldots, N$。 - $T$ 的每条边都有一个在 $0$ 到 $10^9$ 之间（含）的整数权重。 ### 阶段 2 给定一个整数 $Q$，随后是 $Q$ 个整数 $x_1, x_2, \ldots, x_Q$。对于每个 $i$（$1 \leq i \leq Q$），你必须将 $x_i$ 表示为 $T$ 中至多 5 条路径的权重之和。 形式化地说，对于每个 $i$，你必须输出： - 一个整数 $K$（$1 \leq K \leq 5$）， - 以及 $K$ 对顶点 $(u_1, v_1), (u_2, v_2), \ldots, (u_K, v_K)$， 使得 $$\begin{aligned} \sum_{j=1}^{K} w(u_j, v_j) = x_i, \end{aligned}$$ 其中 $w(u, v)$ 表示树 $T$ 中顶点 $u$ 和 $v$ 之间路径的权重。 一条路径的权重定义为该路径所包含的所有边的权重之和。 ### 交互过程 交互过程如下： #### 阶段 1 选择一个整数 $N$ 和一棵带权树 $T$，并按以下格式输出： $$\begin{aligned} & N \\ & a_1 \ b_1 \ c_1 \\ & \vdots \\ & a_{N-1} \ b_{N-1} \ c_{N-1} \end{aligned}$$ 每个三元组 $(a_i, b_i, c_i)$ 表示一条连接顶点 $a_i$ 和 $b_i$ 且权重为 $c_i$ 的边。必须满足以下条件： - $2 \leq N \leq 65$ - $1 \leq a_i, b_i \leq N \quad (1 \leq i \leq N - 1)$ - $0 \leq c_i \leq 10^9 \quad (1 \leq i \leq N - 1)$ #### 阶段 2 首先，会给定一个整数 $Q$（$1 \leq Q \leq 10\,000$）。然后，$Q$ 个整数 $x_1, x_2, \ldots, x_Q$（$1 \leq x_i \leq 10^9$）会逐个给出。对于每个整数 $x_i$，你必须按以下格式输出你的答案： $$\begin{aligned} & K \\ & u_1 \ v_1 \\ & \vdots \\ & u_K \ v_K \end{aligned}$$ 这里 $K$（$1 \leq K \leq 5$）是路径的数量，每对 $(u_j, v_j)$ 表示顶点 $u_j$ 和 $v_j$ 之间的一条路径。 请注意，$x_i$（$i \geq 2$）的值只会在 $x_{i-1}$ 的答案被打印后才会提供。 ### 关于交互评测的说明 如果在交互过程中输出格式错误，或者你的程序提前退出，评测结果将不确定。请在打印答案后立即终止程序，否则评测结果将不确定。由于某些环境需要刷新输出缓冲区，请确保你的输出确实被发送。否则，你的输出将永远不会到达评测机。

无

无

翻译由 DeepSeek V3.2 完成