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 - Maximum White Subtree. 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.

**Simple dfs solution**

But 1324F - Maximum White Subtree 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$$$.*

**Simple dfs solution (using treeDP template)**

Now, all that remains to solve the full problem is to switch out treeDP function with the ultimate reroot template. It returns the output of treeDP **for every node** $$$u$$$, in $$$O(n \log n)$$$ time! It is just that easy. 240129139

**Solution to problem F using the ultimate reroot template**

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 - Maximum White Subtree 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:

**Solution to problem F if both edges and nodes are colored**

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

Python 240150642, C++ 240130674, 219D - Choosing Capital for Treeland

Python 240150668, C++ 240130635, 543D - Road Improvement

Python 240150708, C++ 240130592, 627D - Preorder Test

Python 240150734, C++ 240130838, 852E - Casinos and travel

Python 240150756, C++ 240130918, 960E - Alternating Tree

Or alternatively using "edge DP": Python 240150781, C++ 240131037

Python 240150804, C++ 240131105, 1092F - Tree with Maximum Cost

Python 240150829, C++ 240131161, 1182D - Complete Mirror

Python 240150852, C++ 240131416, 1187E - Tree Painting

Python 240150867, C++ 240131453, 1324F - Maximum White Subtree

Python 240150889, C++ 240131551, 1498F - Christmas Game

Python 240150910, C++ 240131643, 1626E - Black and White Tree

Python 240150929, C++ 240131727, 1691F - K-Set Tree

Python 240150943, C++ 240131762, 1881F - Minimum Maximum Distance

## 3. Understanding the `rerooter`

black box

The following is the black box `rerooter`

implemented naively:

**Template (naive O(n^2) version)**

`rerooter`

outputs three variables.

`rootDP`

is a list, where`rootDP[node] = dfs(node)`

.`forwardDP`

is a list of lists, where`forwardDP[node][eind] = dfs(nei, node)`

, where`nei = graph[node][eind]`

.`reverseDP`

is a list of lists, where`reverseDP[node][eind] = dfs(node, nei)`

, where`nei = 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.

**Rerooting using exclusivity (O(sum deg^2) version)**

## 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*.

**Example: Exclusive segment tree of size n = 8**

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:

**Rerooting using exclusivity (O(sum deg log(deg)) version)**

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!

**Rerooting using exclusivity (O(sum deg log(deg)) version with BFS)**