DYNACON1 - Dynamic Tree Connectivity


A forest of unrooted trees initially consists of N (1 ≤ N ≤ 100,000) single-vertex trees. The vertices are numbered from 1 to N.

Your task is to maintain that forest and answer connectivity queries.

All edges in the problem are undirected.

You will receive the following queries, where (1 ≤ A, B ≤ N) :

  • add A B : add an edge between vertices A and B, where initially there is no path between A and B.
  • rem A B : remove edge between vertices A and B, where initially there is an edge between A and B.
  • conn A B : print YES if there is a path between A and B and NO otherwise, where A and B are different.


The first line of input contains the number of initial single-vertex trees N and the number of queries M (1 ≤ M ≤ 100,000). The following M lines contain queries.


For each conn query output YES or NO. Pay attention to letter case.


5 11
conn 1 5
add 1 2
add 1 3
add 3 4
add 5 4
conn 1 5
rem 4 5
conn 1 5
rem 3 4
add 3 5
conn 1 5


This example will be the first test case.

hide comments
fabijanb: 2019-02-13 20:31:54

very weak test cases, gives AC with a solution that fails on some easy cases

[Rampage] Blue.Mary: 2016-03-22 16:18:56

Test case is too weak. A silly (LCT-like) brute-force approach can get AC.

bakaniner: 2016-02-24 12:47:33

got AC with Union-Find Sets in 0.07s :)

dacin21: 2015-12-11 18:16:54

Great problem to test my Euler-Tour-Tree implementation (although it's armortized O(M*lg^2(N)) ) based on splay-trees!
EDIT: got it down to armortized O(M*lg(n))

Last edit: 2016-01-27 18:34:36
Chiang sheng wen: 2015-12-08 08:29:10

Finally got Accepted with Link/Cut Tree implemented with Treap!

ZiYuan: 2012-08-18 10:55:53

Happy to see the time constraint once became 1600s but now drops to 60s

Last edit: 2011-09-26 22:38:17
:D: 2012-08-18 10:55:53

N*N/8 for N=10^5 is 1.25*10^9. That's over a gigabyte in a single array! Memory limit on SPOJ is 256 MB. Even if it was few GB, I'm not sure the system would be able to allocate that big of a structure.

Bojan Rosko: 2012-08-18 10:55:53

it's giving me sigsegv... I've checked it on ideone.com, and it didn't reported any problems. I have in my code an array of (N*N/8) bytes, but it shouldn't be a problem...

Siarhei Kulik: 2012-08-18 10:55:53

Why the TL is so huge? It seems that even O(M*N) can pass. There is O(M*lg(M)) solution for any kind of undirected graph, not only for trees.

Last edit: 2011-09-25 14:50:34
xiaodao: 2012-08-18 10:55:53

..But this is a unrooted tree..
I am search for tough Problem,
that only can be solved by Link-Cut Tree,
or only can be solved by Heavy-Light Decomposition ..

If you have some one .. Please emaild me ..

Last edit: 2011-09-27 15:51:55

Added by:Andrey Naumenko
Time limit:0.395s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64