mujtaba1747's blog

Problem Suggestion for Tree Flattening
By mujtaba1747, history, 4 years ago, In English

I recently got to know about Tree Flattening using a DFS Traversal. Can someone suggest some nice problems on the same. Thanks!

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Recent,very good problem from July long challenge.Chef and Dragon Dens

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

    I solved that one using 3 Segment Trees :/

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      It can be done with two Binary Indexed Trees.

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

        Yeah actually the third SegTree was for RMQ ...

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Uh? It is just saying the value at some position and update a range by adding a value to all elements in the range. It just a BIT/SegmentTree; since there are queries forward and backward you need two BIT/ST.

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

            Yeah, I used 2 Lazy Segment Trees for Queries (Foward and Backward).

            I used 3rd Segment tree for finding Largest Height between any range [L, R]. (Which is basically a RMQ — Range Maximum Query)

            → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      After flattening?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        No, I did not flatten the Tree in that question. I used a Prefix-Sum Like Approach to solve the problem.

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

          Initially I tried to do same, but I wasn't able to handle update query in log(n) so I got only 45 pts. What was your logic?

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

            Lazy Updates can be done in O(logN).

            And also, it is important to notice that heights are fixed.

            The updates are on the tastiness only.

            → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        let's say $$$dp[u]$$$ is the sum of values of nodes on the path from root downto $$$u$$$. When an updates comes (sum a value of $$$x$$$ to the value of node $$$u$$$), $$$dp[v] \ \forall v\in subtree(u)$$$ are affected with a $$$+x$$$ increase, and when a query $$$u\rightarrow v$$$ comes (with $$$u$$$ ancestor of $$$v$$$), you just have to return $$$dp[v]-dp[parent[u]]$$$. So, by performing a preorder trasversal each subtree becomes a subarray of the euler tour array, so the operations become now: sum $$$x$$$ to all values in a range $$$[l\dots r]$$$ and get the value at some position $$$p$$$; this can be done with Binary Indexed Tree + Difference Array or with Segment Tree + Lazy Propagation (both in $$$O(\log n)$$$ time and $$$O(n)$$$ space).

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

          If I'm not wrong this is what we do in tree flatenning.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            yes, that is a way of flatenning the tree. There are other ways with different uses. For example: to query LCA in $$$O(1)$$$ with SparseTable-preprocessing, you can insert each node $$$u$$$ on the array when you visit it by first time and after you finish processing each one of $$$u$$$'s children; let's say $$$pos[u]$$$ is a position of $$$u$$$ on the euler-tour array. then the $$$LCA(u,v)$$$ is the node with lowest level in the subarray $$$[pos[u]\dots pos[v]]$$$.

            Another way of doing it is with BFS, so the nodes of same level form a subarray of the built array.

            Another way of doing it is with DFS inserting the nodes the first time we visit it and when we goes out of its subtree. This is used to apply Mo's algorithm on trees

            Another way is HLD, this is very useful to apply queries and updates over paths on a tree.

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

try this, this and this

→ Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Hey bro I got a good one https://oj.uz/problem/view/APIO13_toll it uses tree flattening.

→ Reply