RestingRajarshi's blog

Usefulness of the DSU tree over LCT
By RestingRajarshi, 5 years ago, In English

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)

Brief idea about Reachability tree for those too bored to read the editorial linked:

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.

(https://discuss.codechef.com/t/tulips-editorial/12281)

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In such problem, you can use euler cycle on tree and sparse table or segment tree to find minimum between l and r.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you mean like the thing suggested in the editorial itself. making a euler tour and converting it into a range query problem?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +80 Vote: I do not like it

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 right
Cwhtc: Okay if you can code anything... anything right?
Lct: Damn right
Cwhtc: Code this muthaf**kin problem... code that
Lct: I can't do that~ I gotta go through the template~ I haven't used no template in last 6 months
Cwhtc: Well looks like Muthaf**kin Purple can't code a muthaf**ukin problem
Lct: You racist muthafuk-
Cwhtc: Rt, show them how it's done
Rt: Yeah I can code this problem
Cwhtc: That's my boy right there... can fu*kin do anything
Rt: You want me to say the words?
Cwhtc: Be gentle with those words
Rt: You wana know what my solution... COMES WITH?
Cwhtc: Ah sh*t it's comin
Rt: 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 = Rt
    Reference
→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

hint

But I don't know how to solve this with LCT or something similar.

Sorry for my poor English.

→ Reply