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 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
davele:
2024-11-13 14:04:47
The limit is 2*10^5, not 10^5 |
|
narek:
2024-07-04 15:22:22
getting tle for log(n)*log(n) queries and nlog(n)loglog(n) build.
|
|
mestu_paul:
2023-11-02 07:16:17
yeah it is spoj, that's why i didn't got AC in one submission
|
|
sleepntsheep:
2023-09-02 08:03:53
O(N * lg(N) + Q * lg(N)^2)) TLE :( Last edit: 2023-09-02 08:08:07 |
|
saiprasad_27:
2022-06-20 01:27:04
mine using Centroid decomposition and multiset passed in 1.25secs when the time limit being 1s:).
|
|
nafis_shahriar:
2021-07-06 09:05:54
@cichipi_ Thanks, didn't know that about multiset. |
|
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 |
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 |