### RestingRajarshi's blog

By RestingRajarshi, 3 years ago,

I was learning DSU tree (also sometimes known as Reachability Tree) recently (see link below) but the most useful application that I could think was for finding maximum/minimum edge in path from some node A to B. However, this can also be done in O(log N) time using Link Cut Trees.

I was wondering if there was anything that can be done by this DSU-tree/Reachability Tree data structure that can't already be done by LCT.

(I am not that well versed with applications of LCT)

Basically, when we iterate over the edges in a tree in order of weight, we also maintain which edge is connecting which component. So suppose an edge e connects components A and B, we create a new node signifying e and attach to its children A and B. Thus it forms a binary tree, with the leaves as the original nodes, and the n-1 internal edges are basically edges in the normal tree.

• +17

 » 3 years ago, # | ← Rev. 2 →   0 In such problem, you can use euler cycle on tree and sparse table or segment tree to find minimum between l and r.
•  » » 3 years ago, # ^ |   0 you mean like the thing suggested in the editorial itself. making a euler tour and converting it into a range query problem?
•  » » » 3 years ago, # ^ |   0 Yes thing such in editorial. I believe that in each problem that can be solved by LCT, exist easier solution. Such an euler tour in this problem. But if you didn't find any solution without persistant dsu, it is good proposal to think about solution with LCT
•  » » » » 3 years ago, # ^ |   0 I am not looking for problems where both methods can be used, I am looking, rather, for problems which are inherently more suited to reachability trees that to Link-Cut-Trees.
 » 3 years ago, # | ← Rev. 4 →   +80 Sell me this ds's usefulness scene from arXiv.org-Cwhtc: Do you guys not wana lose some pain from the ass? I mean like Do you guys not wana lose some f**king pain from the ass?Lct: I wanna lose some pain. Okay, I can code anything. I can lambda-template myself with great f**king UI.Cwhtc: There we go... That's the attitude... right there... You can code anything right?Lct: Damn rightCwhtc: Okay if you can code anything... anything right?Lct: Damn rightCwhtc: Code this muthaf**kin problem... code thatLct: I can't do that~ I gotta go through the template~ I haven't used no template in last 6 monthsCwhtc: Well looks like Muthaf**kin Purple can't code a muthaf**ukin problemLct: You racist muthafuk-Cwhtc: Rt, show them how it's doneRt: Yeah I can code this problemCwhtc: That's my boy right there... can fu*kin do anythingRt: You want me to say the words?Cwhtc: Be gentle with those wordsRt: You wana know what my solution... COMES WITH?Cwhtc: Ah sh*t it's cominRt: Free... Tree-Binarizing... Mutha... Fu**k a a aa aaa aaaaa aaaaaaaa aaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa Contestant Who Hates To Code = Cwhtc Link/cut Tree = Lct Reachability Tree = RtReference
•  » » 3 years ago, # ^ |   +2 CF needs to have a haha react XD
 » 3 years ago, # |   +10 I think the most useful application of the DSU tree is that you can rearrange reachable nodes under some limits into a subtree or an interval. Then you can maintain the information with some interval data structures. That's what you can't do with LCT.For example, for the problem IOI2018 werewolf, you can solve it with a dsu tree. hintBuild two dsu trees on the graph to rearrange available nodes to perform the transformation into the intersection of two intervals then you can solve it with some 2D counting data structures.But I don't know how to solve this with LCT or something similar. Sorry for my poor English.