samsoom's blog

No binary lifting/LCA tag
By samsoom, history, 16 months ago, In English

Hi,

Why isn't there a binary lifting/LCA tag? I mean it's an important topic, and I'm sure many questions can be solved using them. Can u pls add one?

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

»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

but trees , dfs and similar commonly involves it

→ Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    True but there are a lot of questions that are solved purely by binary lifting/ lca. I js feel that it needs to be classified as a topic by itself

    → Reply
    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      but something that I feel is that many topics if they are directly embedded in the topic section of the problem ,then the problem becomes very vague and less enjoyable . Also lca/lifting both involves dfs at a point , so dfs and 'similar ' already covers all the tree algorithms

      → Reply
      • »
        »
        »
        »
        16 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Yes but when u want to grasp a topic well the best way to do it is to solve specific questions that include that topic. As for lca/lifting involving dfs, binary lifting has 0 dfs in it, and the dfs in lca is only used for the in/out time, the lca/lifting itself is nothing like dfs, they are super unrelated to each other

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          by theory , yes they are unrelated , but for learning part there are multiple other resources , USACO provides good questions topic wise .

          → Reply
          • »
            »
            »
            »
            »
            »
            16 months ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Yes true, USACO does provide good questions. But at the end of the day we come to the same conclusion that LCA/binary lifting doesn't fall under the category of dfs and similar. Anyways idt they'll put a tag lol, but it was a good try nonetheless.

            → Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

even Cses, one of the most educational websites for cp doesn't have a list specially for lifting/LCA.

→ Reply
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    yea but they also don't have a shortest path list even though there's a shortest path tag on cf.

    → Reply