Road_Lighting — OOI qualification
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 25
Algorithms: link-cut tree, tree dp, dynamic programming

# Road Lighting

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 2 seconds       |
| Memory limit: | 512 megabytes   |

Berland is a country with a not very developed road system. There are a total of $n$ cities in Berland and $n - 1$ bidirectional roads, the $i$-th of which connects cities $v_i$ and $u_i$. It is known that between every pair of cities, it is possible to reach one another using only these roads.

It is currently night in Berland, and some roads need to have their lighting turned on. There is a law, created for the purpose of saving electricity, that prohibits turning on the lighting simultaneously on two roads that share a common endpoint. The residents of Berland are interested in the maximum number of roads on which lighting can be turned on without violating the law, so they have turned to you for help.

Unfortunately, in Berland, some roads may be affected by a heavy snowstorm, which can disrupt the connectivity between some pairs of cities. Initially, no road is affected by a snowstorm. There are $q$ queries of two types:

*   Change the weather on road $e_i$ ($1 \le e_i \le n - 1$): if there is currently no snowstorm on road $e_i$, a snowstorm begins, and vice versa.
*   It is required to turn on the lighting on the maximum number of roads such that both endpoints can be reached from city $x_i$, using only the roads that are not affected by a snowstorm. Of course, lighting can be turned on without violating the law, meaning there should not be a pair of roads with lighting turned on that exit from the same city. In other words, the original problem needs to be solved while considering only the cities reachable from $x_i$ via roads that are not affected by a snowstorm.

## Input

The first line contains a single integer $g$ ($0 \le g \le 7$) — the group number for this test.

The second line contains a single integer $n$ ($2 \le n \le 300\,000$) — the number of cities.

The next $n - 1$ lines describe the roads. The $i$-th line contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$) the numbers of the cities connected by the $i$-th road. It is guaranteed that between every pair of cities, it is possible to reach one another using only these roads.

The following line contains a single integer $q$ ($1 \le q \le 300\,000$) — the number of queries.

In the next $q$ lines, the queries are specified. The $i$-th line begins with an integer $t_i$ ($1 \le t_i \le 2$).

*   If $t_i = 1$, then this is a query of the first type, followed by a single integer $e_i$ ($1 \le e_i \le n - 1$) the number of the road on which the weather changes.
*   If $t_i = 2$, then this is a query of the second type, followed by a single integer $x_i$ ($1 \le x_i \le n$). In this case, the original problem needs to be solved while considering only the cities reachable from $x_i$ via roads that are not affected by a snowstorm.

## Output

For each query of the second type, output the maximum number of roads connecting cities reachable from $x_i$ on which lighting can be turned on without violating the law.

## Example

| standard input | standard output |
|----------------|-----------------|
| 0              | 3               |
| 8              | 4               |
| 1 2            | 3               |
| 2 3            | 1               |
| 2 4            |                 |
| 4 5            |                 |
| 1 6            |                 |
| 6 7            |                 |
| 7 8            |                 |
| 8              |                 |
| 1 7            |                 |
| 2 1            |                 |
| 1 7            |                 |
| 2 1            |                 |
| 1 3            |                 |
| 2 3            |                 |
| 1 5            |                 |
| 2 6            |                 |

## Note

In the test example, Berland initially has the following structure:

![](_page_1_Figure_4.jpeg)

After the first query, a snowstorm begins on the road between cities 7 and 8. Then a query comes regarding city 1. In this case, we consider all cities except for city 8, as it is not reachable from city 1. Below is one of the optimal ways to turn on the lighting on the roads (the roads with lighting turned on are marked in red):

![](_page_2_Figure_0.jpeg)

The next query indicates that the snowstorm on the road between cities 7 and 8 ends, meaning everything returns to its original state.

In the very last query, from vertex 6, only vertices 6, 7, and 8 are reachable, so lighting can be turned on at most on one road, for example:

![](_page_2_Figure_3.jpeg)

## Scoring

The tests for this problem consist of seven groups. Points for each group are awarded only if all tests of the group and all tests of some of the previous groups are passed. Note that passing the samples is not required for some groups. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Points | Additional Constraints |   | Required Groups | Comment                                             |
|-------|--------|------------------------|---|-----------------|-----------------------------------------------------|
|       |        | $n$                      | $q$ |                 |                                                     |
| 0     | 0      | –                      | – | –               | Samples.                                            |
| 1     | 14     | $n \le 100$            | $q \le 100$      | 0               |                                                     |
| 2     | 13     | $n \le 100\,000$        | $q \le 100\,000$  | –               | $v_i = i, u_i = i + 1$                              |
| 3     | 10     | $n \le 100\,000$        | $q = 1$        | –               |                                                     |
| 4     | 12     | $n \le 100\,000$        | $q \le 100\,000$  | –               | $v_i = i + 1, u_i = \lfloor \frac{v_i}{2} \rfloor$ |
| 5     | 19     | $n \le 100\,000$        | $q \le 100\,000$  | 3               | The snowstorm cannot end                            |
| 6     | 20     | $n \le 100\,000$        | $q \le 100\,000$  | 0 – 5           |                                                     |
| 7     | 12     | –                      | – | 0 – 6           | Offline-testing.                                    |

Starter code: