Particle Collision Experiments on a Tree

We are given an unrooted tree with n nodes (numbered from 0 to n-1) and q operations. Initially, no node has a particle. In each operation, you are given a node u and a boolean result. If result is true, a particle is generated at node u; if false, node u is closed (and can never be used later). It is guaranteed that each node is attempted at most once.

After every generation attempt, you must answer the following question:

What is the maximum number of collision experiments that can be performed?

A collision experiment is defined as follows: Choose two different nodes u and v such that:

• Both u and v currently have a particle.
• On the unique simple path connecting u and v (in the tree with all closed nodes removed), there are no particles except at the endpoints.
• On that same path, no node is closed.

After a collision experiment, the particles at u and v are destroyed. (Note that this is only a theoretical experiment – the particles are not actually removed in the state.)

For example, consider a tree with 3 nodes connected as 0-1-2. If particles are generated at nodes 0 and 2 and node 1 is empty, then a collision experiment between 0 and 2 is possible since the intermediate node (1) is empty and open. However, if node 1 also has a particle, then collisions can only be performed, say, between 0 and 1 or between 1 and 2, so that the maximum number of simultaneous collisions (when scheduled one after the other) is 1.

Note: The indices are 0-indexed. Also, the collision experiments are theoretical – you only need to output the maximum number of experiments possible after each particle generation attempt.

Mathematical formulation:

Let \(T\) be a tree with n nodes. Let S be the set of nodes that currently have a particle and let \(G_{open}\) be the subgraph of T obtained by removing all closed nodes. For any two nodes \(u,v \in S\) that lie in the same connected component of \(G_{open}\), a collision is possible if the unique path between \(u\) and \(v\) in \(G_{open}\) satisfies \[ \{w \in P(u,v) \setminus \{u,v\} : w \in S\} = \emptyset. \]

Determine the maximum number of pairwise disjoint collisions (i.e. a maximum matching among the "visible" particle nodes) that can be arranged.

inputFormat

The system will call two functions:

void initialize(int n, vector<int> A, vector<int> B);
int generate(int u, bool result);

The function initialize is called once with:

• n: the number of nodes in the tree.
• A and B: two arrays of length n-1 describing the edges of the tree. For each index i (0-indexed), there is an edge between nodes A[i] and B[i].

After that, the function generate is called exactly q times. Each call provides:

• u: the node where a particle generation is attempted.
• result: a boolean indicating the outcome. If true, a particle is generated; if false, node u is closed.

After each call to generate, you must return a non-negative integer representing the maximum number of collision experiments that can be performed given the current state.

outputFormat

After each call to generate, output a single non-negative integer indicating the maximum number of collision experiments possible.

sample

5
0 0 1 1
1 2 3 4
4
0 true
3 true
1 false
4 true

0
1
0
0