P15763 [JAG 2025 Summer Camp #1] Billion Tree

This is an interactive problem. The interaction consists of two phases. ### Phase 1 You must first choose an integer $N$ ($2 \leq N \leq 65$). Then you must output the chosen $N$ and a tree $T$ on $N$ vertices satisfying the following conditions: - The vertices are numbered $1, 2, \ldots, N$. - Each edge of $T$ has an integer weight between $0$ and $10^9$, inclusive. ### Phase 2 You are given an integer $Q$, followed by $Q$ integers $x_1, x_2, \ldots, x_Q$. For each $i$ ($1 \leq i \leq Q$), you must express $x_i$ as the sum of the weights of at most 5 paths in $T$. Formally, for each $i$ you must output: - an integer $K$ ($1 \leq K \leq 5$), - and $K$ pairs of vertices $(u_1, v_1), (u_2, v_2), \ldots, (u_K, v_K)$, such that $$\begin{aligned} \sum_{j=1}^{K} w(u_j, v_j) = x_i, \end{aligned}$$ where $w(u, v)$ denotes the weight of the path between vertices $u$ and $v$ in $T$. The weight of a path is defined as the sum of the weights of the edges contained in the path. ### Interaction The interaction proceeds as follows: #### Phase 1 Choose an integer $N$ and a weighted tree $T$, and output them in the following format: $$\begin{aligned} & N \\ & a_1 \ b_1 \ c_1 \\ & \vdots \\ & a_{N-1} \ b_{N-1} \ c_{N-1} \end{aligned}$$ Each triple $(a_i, b_i, c_i)$ represents an edge between vertices $a_i$ and $b_i$ with weight $c_i$. The following conditions must hold: - $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)$ #### Phase 2 First, an integer $Q$ ($1 \leq Q \leq 10\ 000$) is given. Then, $Q$ integers $x_1, x_2, \ldots, x_Q$ ($1 \leq x_i \leq 10^9$) are given one by one. For each integer $x_i$, you must output your answer in the following format: $$\begin{aligned} & K \\ & u_1 \ v_1 \\ & \vdots \\ & u_K \ v_K \end{aligned}$$ Here $K$ ($1 \leq K \leq 5$) is the number of paths, and each pair $(u_j, v_j)$ represents a path between vertices $u_j$ and $v_j$. Note that the value $x_i$ ($i \geq 2$) is provided only after the answer for $x_{i-1}$ has been printed. ### Notes on Interactive Judging The verdict will be indeterminate if there is malformed output during the interaction or your program quits prematurely. Terminate the program immediately after printing the answer, or the verdict will be indeterminate. As some environments require flushing the output buffers, make sure that your outputs are actually sent. Otherwise, your outputs will never reach the judge.

N/A

N/A