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

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 15:16:40 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

I solved that one using 3 Segment Trees :/

It can be done with two Binary Indexed Trees.

Yeah actually the third SegTree was for RMQ ...

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.

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)

After flattening?

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

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?

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.

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).

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

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.

Thanks for this knowledge.

Thanks !

try this, this and this

Thanks a lot !

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

Thanks !