QTREE3  Query on a tree again!
English  Vietnamese 
You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. In the start, the color of any node in the tree is white.
We will ask you to perfrom some instructions of the following form:
 0 i : change the color of the ith node (from white to black, or from black to white);
or  1 v : ask for the id of the first black node on the path from node 1 to node v. if it doesn't exist, you may return 1 as its result.
Input
In the first line there are two integers N and Q.
In the next N1 lines describe the edges in the tree: a line with two integers a b denotes an edge between a and b.
The next Q lines contain instructions "0 i" or "1 v" (1 ≤ i, v ≤ N).
Output
For each "1 v" operation, write one integer representing its result.
Example
Input: 9 8 1 2 1 3 2 4 2 9 5 9 7 9 8 9 6 8 1 3 0 8 1 6 1 7 0 2 1 9 0 2 1 9 Output: 1 8 1 2 1
Constraints & Limits
There are 12 real input files.
For 1/3 of the test cases, N=5000, Q=400000.
For 1/3 of the test cases, N=10000, Q=300000.
For 1/3 of the test cases, N=100000, Q=100000.
hide comments
luka_dzimba911:
20181204 17:54:35
2.8sec AC where am i using too much time I have HLD with segment Last edit: 20181204 17:55:08 

phoemur:
20181126 01:32:06
Solved with HeavyLight Decomposition + std::set for each chain.


khaled97ha:
20180820 18:16:32
what's the wrong if i'am getting 41.67 ?


Lucas Amaral Damaso:
20180731 00:52:49
notice: you should read until end of file. 

siva2697:
20180225 08:28:51
NICE BASIC HLD. 

sherlock726:
20171230 19:21:43
you can solve it without HLD


harshit_saini:
20171229 04:19:52
Is it possible to solve this problem using centroid decomposition? 

magolor:
20170511 13:29:20
Notice that "first" in query means the one with min depth. 

amandal799:
20170326 19:15:13
100 in second go !! simple HLD 

yousiki:
20170123 03:17:37
Why I got 100 instead of AC? 
Added by:  Fudan University Problem Setters 
Date:  20080614 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  VNOI Marathon '08  Round 6/DivA Problem Setter: Blue Mary 