Hi Codeforces!
Have you ever had this issue before?
If yes, then you have come to the right place! This is a blog about my super easy to use template for (reroot) DP on trees. I really believe that this template is kind of revolutionary for solving reroot DP problems. I've implemented it both in Python and in C++ (the template supports Python2, Python3 and >= C++14). Using this template, you will be able to easily solve > 2000 rated reroot problems in a couple of minutes, with a couple of lines of code.
A big thanks goes out to everyone that has helped me by giving feedback on blog and/or discussing reroot with me, nor, meooow, qmk, demoralizer, jeroenodb, ffao. And especially a huge thanks goes to nor for helping out making the C++ version of the template.
1. Introduction / Motivation
As an example, consider this problem: 1324F - Максимально белое поддерево . The single thing that makes this problem difficult is that you need for every node $$$u$$$ find the maximum white subtree containing $$$u$$$. Had this problem only asked to find the answer for a specific node $$$u$$$, then a simple dfs solution would have worked.
But 1324F - Максимально белое поддерево requires you to find the answer for every node. This forces you to use a technique called rerooting. Long story short, it is a mess to code. Maybe you could argue that for this specific problem it isn't all that bad. But it is definitely not as easy to code as the dfs solution above.
What if I told you that it is possible to take the logic from the dfs function above, put it inside of a "black box", and get the answer for all $$$u$$$ in $$$O(n \log n)$$$ time? Well it is, and that is what this blog is all about =)
In order to extract the logic from the simple dfs solution, let us first create a generic template for DP on trees and implement the simple dfs solution using its interface. Note that the following code contain the exact same logic as the simple dfs solution above. It solves the problem for a specific node $$$u$$$.
Now, all that remains to solve the full problem is to switch out the treeDP function with the ultimate reroot template. The template returns the output of treeDP for every node $$$u$$$, in $$$O(n \log n)$$$ time! It is just that easy. 240150867
The takeaway from this is example is that the reroot template makes it almost trivial to solve complicated reroot problems. For example, suppose we modify 1324F - Максимально белое поддерево such that both nodes and edges have colors. Normally this modification would be complicated and would require an entire overhaul of the solution. However, with the ultimate reroot template, the solution is simply:
2. Collection of reroot problems and solutions
Here is a collection of reroot problems on Codeforces, together with some short and simple solutions in both Python and C++ using the rerooter template. These are nice problems to practice on if you want to try out using this template. The difficulty rating ranges between 1700 and 2600. I've also put together a GYM contest with all of the problems: Collection of Reroot DP problems (difficulty rating 1700 to 2600).
- (1700 rating) 219D - Выбор столицы Древляндии
- Python solution, C++ solution
- (2300 rating) 543D - Улучшение дорог
- Python solution, C++ solution
- (2200 rating) 592D - Супер М
- Python solution, C++ solution
- (2600 rating) 627D - Тестирование дерева
- Python solution, C++ solution
- (2100 rating) 852E - Казино и путешествия
- Python solution, C++ solution
- (2300 rating) 960E - Знакопеременное дерево
- Python solution, C++ solution
- Or alternatively using "edge DP":
- Python solution, C++ solution
- (1900 rating) 1092F - Дерево максимальной стоимости
- Python solution, C++ solution
- (2200 rating) 1156D - 0-1-Дерево
- Python solution, C++ solution
- (2400 rating) 1182D - Полное зеркало
- Python solution, C++ solution
- (2100 rating) 1187E - Покраска дерева
- Python solution, C++ solution
- (2000 rating) 1294F - Три пути в дереве
- Python solution, C++ solution
- (1800 rating) 1324F - Максимально белое поддерево
- Python solution, C++ solution
- (2500 rating) 1498F - Рождественская игра
- Python solution, C++ solution
- (2400 rating) 1626E - Черно-белое дерево
- Python solution, C++ solution
- (2500 rating) 1691F - Дерево и k-подмножества
- Python solution, C++ solution
- (2400 rating) 1794E - Разметка дерева расстояниями
- Python solution, C++ solution
- (2500 rating) 1796E - Красивые подграфы
- Python solution, C++ solution
- (1700 rating) 1881F - Минимальное максимальное расстояние
- Python solution, C++ solution
- 104008G - Group Homework
- Python solution, C++ solution
- 104665H - Alice Learns Eertree!
- Python solution, C++ solution
3. Understanding the rerooter black box
The following is the black box rerooter implemented naively:
rerooter outputs three variables.
rootDPis a list, whererootDP[node] = dfs(node).forwardDPis a list of lists, whereforwardDP[node][eind] = dfs(nei, node), wherenei = graph[node][eind].reverseDPis a list of lists, wherereverseDP[node][eind] = dfs(node, nei), wherenei = graph[node][eind].
If you don't understand the definitions of rootDP/forwardDP/reverseDP, then I recommend reading the naive $$$O(n^2)$$$ implementation of rerooter. It should be fairly self explanatory.
The rest of this blog is about the techniques of how to make rerooter run in $$$O(n \log n)$$$. So if you just want to use rerooter as a black box, then you don't have to read or understand the rest of this blog.
One last remark. If you've ever done rerooting before, you might recall that rerooting usually runs in $$$O(n)$$$ time. So why does this template run in $$$O(n \log n)$$$? The reason for this is that I restrict myself to use the combine function in a left folding procedure, e.g. combine(combine(combine(nodeDP, neiDP1), neiDP2), neiDP3). My template is not allowed to do for example combine(nodeDP, combine(neiDP1, combine(neiDP2, neiDP3))). While this limitation makes the template run slower, $$$O(n \log n)$$$ instead of $$$O(n)$$$, it also makes it a lot easier to use the template. If you still think that the $$$O(n)$$$ version is superior, then I don't think you've understood how nice and general the $$$O(n \log n)$$$ version truly is.
4. Rerooting and exclusivity
The general idea behind rerooting is that we first compute the DP as normal for some arbitrary node as the root (I use node = 0 for this). After we have done this we can "move" the root of the tree by updating the DP value of the old root and the DP value of a neighbour to the old root. That neighbour then becomes the new root.
Let $$$u$$$ denote the current root, and let $$$v$$$ denote the neighbour of $$$u$$$ that we want to move the root to. At this point, we already know the value of dfs(v, u) since $$$u$$$ is the current root. But in order to be able to move the root from $$$u$$$ to $$$v$$$, we need to find the new DP value of $$$u$$$, i.e. dfs(u, v).
If we think about this in terms of forwardDP and reverseDP, then we currently know forwardDP[u], and our goal is to compute reverseDP[u]. This can be done naively in $$$O(\text{deg}(u)^2)$$$ time with a couple of for loops by calling combine $$$O(\text{deg}(u)^2)$$$ times, and then calling finalize $$$O(\text{deg}(u))$$$ times.
The bottle neck here are the $$$O(\text{deg}(u)^2)$$$ calls to combine. So for now, let us separate out the part of the code that calls combine from the rest of the code into a function called exclusive. The goal of the next section will then be to speed up the naively implemented exclusive function to run in $$$O(\text{deg}(u) \text{log} (\text{deg}(u)))$$$ time.
5. The exclusive segment tree
We are almost done implementing the fast reroot template. The only operation left to speed up is the function exclusive. Currently it runs in $$$O(\sum \text{deg}^2)$$$ time. The trick to make exclusive run in $$$O(\sum \text{deg} \log{(\text{deg})})$$$ time is to create something similar to a segment tree.
Suppose you have a segment tree where each node in the segment tree accumulates all of the values outside of its interval. The leaves of such a segment tree can then be used as the output of exclusive. I call this data structure the exclusive segment tree.
The exclusive segment tree is naturally built from top to bottom, taking $$$O(n \log n)$$$ time. Here is an implementation of rerooter using the exclusive segment tree:
This algorithm runs in $$$O(\sum \text{deg} \log{(\text{deg})})$$$, so we are essentially done. However, this implementation uses recursive DFS which especially for Python is a huge drawback. Recursion in Python is both relatively slow and increadibly memory hungry. So for a far more practical version, I've also implemented this same algorithm using a BFS instead of a DFS. This gives us the final version of the ultimate rerooter template!
