Query on a tree VI
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a tree (an acyclic undirected connected graph) with n nodes. The tree nodes are numbered from 1 to n. Each node has a color, white or black. All the nodes are black initially. We will ask you to perfrom some instructions of the following form:
- 0 u: ask for how many nodes are connected to u, two nodes are connected if all the node on the path from u to v (inclusive u and v) have the same color.
- 1 u: toggle the color of u (that is, from black to white, or from white to black).
The first line contains a number n that denotes the number of nodes in the tree (1 ≤ n ≤ 105). In each of the following n-1 lines, there will be two numbers (u, v) that describes an edge of the tree (1 ≤ u, v ≤ n). The next line contains a number m denoting number of operations we are going to process (1 ≤ m ≤ 105). Each of the following m lines describe an operation (t, u) as we mentioned above(0 ≤ t ≤ 1, 1 ≤ u ≤ n).
For each query operation, output the corresponding result.
5 1 2 1 3 1 4 1 5 3 0 1 1 1 0 1 Output 1:
7 1 2 1 3 2 4 2 5 3 6 3 7 4 0 1 1 1 0 2 0 3
7 3 3
Warning: large input/output data,be careful with certain languages
|Tags||dec13, hard, heavy-light, link-cut-tree, xiaodao|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.