LuminaRiddle

5

1 votes
Graphs, Advanced Data Structures, Segment Trees, Data Structures, Euler Tour and Path, Algorithms
Problem

In the depths of a mystical forest stands the "Luminous Tree", having N magical nodes. Each of these nodes possesses the unique capability to glow either in white or black. Initially, all nodes have a white glow.

The tree's structure is well-established, with node 1 serving as its root and (N1) branches connecting the entirety of its nodes.

Travelers, having heard tales of the tree's peculiar characteristics, visit with specific queries. Their queries fall into two distinct categories:

In the First type of query, a traveler can specify a node and request its color to be changed. If the node is presently glowing white, it will be changed to black, and if it's black, it will be changed to white.

In the Second query type, a traveler can specify a node and ask a question about the tree's black-lit nodes. Specifically, they desire to know the maximum distance from their chosen node to any node glowing black in that node's subtree. If there is no black glowing node in the selected node's subtree, then the response for this query is 1.

As the guardian of the Luminous Tree, your mission is to efficiently address these traveler queries, particularly providing the answer for the second type of queries.

Input Format:

  • The first line contains a single integer T, which denotes the number of test cases.
  • For each test case:
    • The first line contains N denoting the number of vertices in the tree.
    • The following N1 lines contain 2 space-separated integers, u and v, indicating that there is an edge between vertices u & v.
    • The following line contains M denoting the number of queries.
    • The following M lines contain 2 space-separated integers, type and x, where type is 1 if the query is of the first type and 2 if the query is of the second type and x is the selected node for the current query.

Output Format:

For each test case, address all the M  queries. For each query of the second type, provide the answer in a new line. Print the answer for each query in a new line. If, for a second type query, there is no black glowing node in the selected node's subtree, then you need to print 1 as the answer for that query.

Constraints:

1T1053N1061u,vN1M106type[1,2]1xN The sum of all values of N over all test cases doesn't exceed 106The sum of all values of M over all test cases doesn't exceed 106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The first line denotes T = 1.

For test case 1:

We are given:

  • N = 6 and the tree is linked as follows:

                

  • M = 3

Now,

  • For the first query, we don't have any nodes in the subtree of node 1, which is black, so the answer is -1.
  • For the Second query, we change node 3's color to black.
  • For the third query, we have just 1 node in the subtree of node 1 (i.e., node 3), which is black, and it is at distance 2 from node 1, so the answer is 2.
  • For the fourth query, we change node 4's color to black.
  • For the fifth query, we have 2 nodes in the subtree of node 1, which are black, and the farthest out of those is at a distance 2 (i.e., node 3) from node 1, so the answer is 2.
  • For the sixth query, we have just 1 node in the subtree of node 4 (i.e., node 4), which is black, and it is at a distance 0 from node 4, so the answer is 0.
Editor Image

?