Close Node

Time: 2.0 s     Memory: 1024 MB
  • A tree on $N$ nodes labeled with integers between $0$ and $N-1$ is given. Initially, all nodes are white, except node $0$ which is black. Your task is to answer two types of queries:

    • Type $0$: given node $u$, change the color of node $u$ from white to black

    • Type $1$: given node $u$, print the distance between $u$ and the closest black node, measured in number of crossed edges

    If a node is given in a query of type $0$, it is guaranteed to be white at that point in time.

    Input

    The first line of input contains the integers $N$ and $Q$ ($1 \leq N,Q \leq 2*10^5$), the number of nodes and queries.

    The following $N-1$ lines each contain the integers $a$ and $b$ ($0 \leq a,b \leq N-1$), which means that there is an edge between node $a$ and $b$. These edges are guaranteed to form a tree.

    Then, the next $Q$ each contain a query. Each query start with the integer $T$.

    If $T=0$, the next integer is $u$ ($0 \leq u \leq N-1$), the node to be changed from white to black.

    If $T=1$, the next integer is $u$ ($0 \leq u \leq N-1$), the node for which we want to know the distance to the nearest black node.

    Output

    For each query where $T=1$, print the smallest number of edges you need to cross to go from node $u$ to a black node.

    Scoring

    Your solution will be tested on multiple testcases. To solve the problem, your solution must solve every testcase correctly.

    Sample Input 1 Sample Output 1
    5 4
    0 1
    1 2
    2 3
    2 4
    1 0
    1 4
    0 3
    1 4
    
    0
    3
    2
    
Centroid decomposition
  •  
  • To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.

    You must log in to register.
  • Close Node
  • Count Nodes
  • Faraway Node
You must log in to submit solutions to the problem.
{"contest_start_timestamp": null, "contest_duration": 86400, "contest_started": true, "contest_ended": true, "flexible_start_window_end_time": null, "only_virtual": true}