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
majju69:
20240122 11:40:03
What does 0 and 41.57 mean in the judge status ? 

c2zi6:
20240105 19:52:00
is there a solution without HLD?


tianjizi:
20230204 03:14:44
replying to llite_27


hieunekodesu:
20230110 15:32:26
hmmm just ett and lazy segment 

llite_27:
20220817 11:51:44
my code using HLD +BIT +Binary Search


evang12:
20220329 02:28:35
You don't need HLD. Just binary lifting and Euler tour are sufficient.


rkas:
20220106 17:22:02
Perfect score is 100 btw. Last edit: 20220106 17:22:38 

princemishra:
20210702 15:18:04
use binary search and hld Last edit: 20210702 15:18:23 
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 