Particle Accelerator

KOI Team Selection Test 2025
Original Statement / Submission Site

Problem Statement

KOI Laboratory conducts research using a particle accelerator. The accelerator consists of N rooms and N - 1 bidirectional passages connecting them. It is possible to travel between every pair of distinct rooms using only these passages. Therefore, the accelerator has the structure of a tree.

The rooms are numbered from 0 to N - 1, and the passages are numbered from 0 to N - 2. For every 0 ≤ i ≤ N - 2, passage i connects rooms A[i] and B[i].

KOI Laboratory is conducting an IOI-particle collision experiment. Because IOI particles are extremely difficult to create, at most one particle-generation attempt may be made in each room.

• If particle generation succeeds in a room, one stationary IOI particle is created there.
• If particle generation fails, that room is closed for equipment inspection and can no longer be used.

After attempting particle generation in several rooms, the laboratory performs a sequence of collision experiments. In each collision experiment, two rooms containing IOI particles are selected. The experiment may be performed only if the path connecting the two selected rooms contains neither another room that currently contains an IOI particle nor a room in which particle generation failed.

After the collision experiment, the two particles used in the experiment disappear.

Note that a room in which particle generation succeeded but whose particle has already disappeared may lie on the path used by a later collision experiment.

Initially, no room contains an IOI particle, and particle generation may be attempted in every room. The laboratory makes a total of Q particle-generation attempts. After each attempt, determine the maximum number of collision experiments that can be performed from the current state.

Task

Implement the functions described below.

Functions to Implement

void initialize(int N, std::vector<int> A, std::vector<int> B)

• N: the number of rooms in the particle accelerator.
• A, B: integer arrays of length N - 1. For every 0 ≤ i ≤ N - 2, there is a passage connecting rooms A[i] and B[i].
• This function is called exactly once at the beginning.

int generate(int v, bool result)

• This function represents a particle-generation attempt in room v.
• It is called exactly Q times after initialize.
• v: the room in which particle generation is attempted. It is guaranteed that no earlier attempt has been made in room v.
• result: if true, particle generation succeeds and room v now contains an IOI particle; if false, particle generation fails and room v is closed.
• The function must return the maximum number of collision experiments that can be performed from the current state.

Constraints

• 2 ≤ Q ≤ N ≤ 200000
• The particle accelerator forms a tree.
• 0 ≤ A[i], B[i] ≤ N - 1
• A[i] ≠ B[i]
• For every call to generate, 0 ≤ v ≤ N - 1.
• All values of v passed to generate are distinct.

Subtasks

Subtask 1 [9 points]

• 2 ≤ Q ≤ N ≤ 5000

Subtask 2 [16 points]

• A[i] = i and B[i] = i + 1 for every 0 ≤ i ≤ N - 2.

Subtask 3 [20 points]

• At most 20 calls to generate have result = false.

Subtask 4 [23 points]

• At most 20 calls to generate have result = true.

Subtask 5 [32 points]

There are no additional constraints.

Example 1

Consider

N = 6
A = [0, 0, 0, 3, 3]
B = [1, 2, 3, 4, 5]

The grader first calls:

initialize(6, [0, 0, 0, 3, 3], [1, 2, 3, 4, 5])

The structure of the particle accelerator is shown below.

First generation attempt

generate(1, true)

Room 1 now contains an IOI particle. No collision experiment can be performed, so the function must return 0.

Second generation attempt

generate(5, true)

Rooms 1 and 5 now contain particles. A collision experiment can be performed using these two rooms. It is impossible to perform two or more experiments, so the function must return 1.

Third generation attempt

generate(0, false)

Room 0 is now closed. Since room 0 lies on the path between rooms 1 and 5, no collision experiment can be performed. The function must return 0.

Fourth generation attempt

generate(4, true)

Rooms 1, 4, and 5 contain particles, while room 0 is closed. A collision experiment can be performed using rooms 4 and 5. It is impossible to perform two or more experiments, so the function must return 1.

Fifth generation attempt

generate(3, true)

Rooms 1, 3, 4, and 5 contain particles, while room 0 is closed. Rooms 4 and 5 cannot be selected together because room 3, which contains a particle, lies on their path. However, rooms 3 and 5 can be selected for a collision experiment.

After colliding the particles in rooms 3 and 5, no further collision experiment is possible. In particular, room 0 lies on the path between rooms 1 and 4. Therefore, it is impossible to perform two or more experiments, and the function must return 1.

Sample Grader

The sample grader reads input in the following format:

N Q
A[0] B[0]
A[1] B[1]
...
A[N-2] B[N-2]
v[0] result[0]
v[1] result[1]
...
v[Q-1] result[Q-1]

For each generation attempt, result is written as 1 for true and 0 for false.

The sample grader prints one line for each call to generate, containing the value returned by that call.

Note that the sample grader may differ from the grader used for actual evaluation.