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 perfrom some instructions of the following form:

  • 0 i : change the color of i-th 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 N-1 lines, the i-th line describes the i-th 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
mhasan01: 2020-07-12 01:23:35

Finally got Accepted :')

kinhosz: 2020-01-18 00:09:45

I know how to solve it using hld

tanmayak99: 2019-12-12 09:55:46

Don't use "long long int" -> gave me TLE

hocky: 2019-04-20 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: 2019-04-20 16:27:57
cichipi_: 2018-10-25 14:24:22

here is aonother similar problem of centroid decomposition
http://codeforces.com/contest/342/problem/E

Last edit: 2018-10-25 14:24:37
cichipi_: 2018-10-25 10:45:58

remember ......
your multiset ms = {1,1,1,3,4}
after calling ms.erase(1) it will be = {3,4}
so do this,
auto it = ms.find(1) ;
ms.erase(it);

got 3 WA for this crap :)

Last edit: 2018-10-25 10:46:14
cichipi_: 2018-10-25 08:32:49

Time limit not even 1s....fuck

Rizvee: 2018-05-10 16:37:48

do O(LogN * LogN) per query get AC ? I am consistently getting TLE. I tried to implement centroid decomposition here.

siva2697: 2018-03-31 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..?

tanavya: 2018-03-05 05:36:29

If anyone wants to learn the algorithm used to solve this problem, read this amazing blog: https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree :)
Note: HLD can also be used, but thats a bit more challenging. :)


Added by:Qu Jun
Date:2008-08-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:XunYunbo, modified from ZJOI07