QTREE5  Query on a tree V
You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. We define dist(a, b) as the number of edges on the path from node a to node b.
Each node has a color, white or black. All the nodes are black initially.
We will ask you to perform some instructions of the following form:
 0 i : change the color of ith node(from black to white, or from white to black).
 1 v : ask for the minimum dist(u, v), node u must be white(u can be equal to v). Obviously, as long as node v is white, the result will always be 0.
Input
 In the first line there is an integer N (N <= 100000)
 In the next N1 lines, the ith line describes the ith edge: a line with two integers a b denotes an edge between a and b.
 In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
 In the next Q lines, each line contains an instruction "0 i" or "1 v"
Output
For each "1 v" operation, print one integer representing its result. If there is no white node in the tree, you should write "1".
Example
Input: 10 1 2 1 3 2 4 1 5 1 6 4 7 7 8 5 9 1 10 10 0 6 0 6 0 6 1 3 0 1 0 1 1 3 1 10 1 4 1 6 Output: 2 2 2 3 0
hide comments
saiprasad_27:
20220620 01:27:04
mine using Centroid decomposition and multiset passed in 1.25secs when the time limit being 1s:).


nafis_shahriar:
20210706 09:05:54
@cichipi_ Thanks, didn't know that about multiset. 

mhasan01:
20200712 01:23:35
Finally got Accepted :') 

kinhosz:
20200118 00:09:45
I know how to solve it using hld 

tanmayak99:
20191212 09:55:46
Don't use "long long int" > gave me TLE 

hocky:
20190420 16:26:51
When decomposing the tree (checking the tree subsize and traversing centroid), remember not to go back to the ones that has been in the decomposed tree Last edit: 20190420 16:27:57 

cichipi_:
20181025 10:45:58
remember ......


cichipi_:
20181025 08:32:49
Time limit not even 1s....fuck 

Rizvee:
20180510 16:37:48
do O(LogN * LogN) per query get AC ? I am consistently getting TLE. I tried to implement centroid decomposition here. 

siva2697:
20180331 15:19:26
BEST QUESTION ON TREES MUST DO. try implementing priority_queue its fun when u get it AC. DID with centroid Decomposition. I wonder how HLD approach would be for this..? 
Added by:  Qu Jun 
Date:  20080813 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  XunYunbo, modified from ZJOI07 