The Ultimate Reroot Template

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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

def dfs(node, parent=-1):
  nodeDP = 0
  for nei in graph[node]:
    if nei != parent:
      nodeDP = nodeDP + max(dfs(nei, node), 0)
  return nodeDP + 2 * color[node] - 1
print(dfs(u))

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)

def treeDP(root, graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
  DP = [0] * len(graph)
  def dfs(node, parent=-1):
    nodeDP = default[node]
    for eind, nei in enumerate(graph[node]):
      if nei != parent:
        neiDP = dfs(nei, node)
        nodeDP = combine(nodeDP, neiDP, node, eind)
    parent_eind = -1 if parent == -1 else graph[node].index(parent)
    DP[node] = finalize(nodeDP, node, parent_eind)
    return DP[node]
  
  dfs(root)
  return DP

default = [0] * n

def combine(nodeDP, neiDP, node, eind):
  return nodeDP + max(neiDP, 0)

def finalize(nodeDP, node, eind):
  return nodeDP + 2 * color[node] - 1

print(treeDP(u, graph, default, combine, finalize)[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

Solution to problem F using the ultimate reroot template

default = [0] * n

def combine(nodeDP, neiDP, node, eind):
  return nodeDP + max(neiDP, 0)

def finalize(nodeDP, node, eind):
  return nodeDP + 2 * color[node] - 1

rootDP, _, _ = rerooter(graph, default, combine, finalize)
print(*rootDP)

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

default = [0] * n

def combine(nodeDP, neiDP, node, eind):
  return nodeDP + max(neiDP + 2 * edge_color[node][eind] - 1, 0)

def finalize(nodeDP, node, eind):
  return nodeDP + 2 * color[node] - 1

rootDP, _, _ = rerooter(graph, default, combine, finalize)
print(*rootDP)

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 - Choosing Capital for Treeland: Python solution, C++ solution
(2300 rating) 543D - Road Improvement: Python solution, C++ solution
(2200 rating) 592D - Super M: Python solution, C++ solution
(2600 rating) 627D - Preorder Test: Python solution, C++ solution
(2100 rating) 852E - Casinos and travel: Python solution, C++ solution
(2300 rating) 960E - Alternating Tree: Python solution, C++ solution; Or alternatively using "edge DP":; Python solution, C++ solution
(1900 rating) 1092F - Tree with Maximum Cost: Python solution, C++ solution
(2200 rating) 1156D - 0-1-Tree: Python solution, C++ solution
(2400 rating) 1182D - Complete Mirror: Python solution, C++ solution
(2100 rating) 1187E - Tree Painting: Python solution, C++ solution
(2000 rating) 1294F - Three Paths on a Tree: Python solution, C++ solution
(1800 rating) 1324F - Maximum White Subtree: Python solution, C++ solution
(2500 rating) 1498F - Christmas Game: Python solution, C++ solution
(2400 rating) 1626E - Black and White Tree: Python solution, C++ solution
(2500 rating) 1691F - K-Set Tree: Python solution, C++ solution
(2400 rating) 1794E - Labeling the Tree with Distances: Python solution, C++ solution
(2500 rating) 1796E - Colored Subgraphs: Python solution, C++ solution
(1700 rating) 1881F - Minimum Maximum Distance: 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:

Template (naive O(n^2) version)

def treeDP(root, graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
  DP = [0] * len(graph)
  def dfs(node, parent=-1):
    nodeDP = default[node]
    for eind, nei in enumerate(graph[node]):
      if nei != parent:
        neiDP = dfs(nei, node)
        nodeDP = combine(nodeDP, neiDP, node, eind)
    parent_eind = -1 if parent == -1 else graph[node].index(parent)
    DP[node] = finalize(nodeDP, node, parent_eind)
    return DP[node]
  
  dfs(root)
  return DP

def rerooter(graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
  n = len(graph)
  rootDP = []
  edgeDP = {}
  for root in range(n):
    DP = treeDP(root, graph, default, combine, finalize)
    rootDP.append(DP[root])
    for nei in graph[root]:
      edgeDP[root, nei] = DP[nei]
    
  forwardDP = [[edgeDP[node, nei] for nei in graph[node]] for node in range(n)]
  reverseDP = [[edgeDP[nei, node] for nei in graph[node]] for node in range(n)]

  return rootDP, forwardDP, reverseDP

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)

def exclusive(A, zero, combine, node):
    n = len(A)

    exclusiveA = [zero] * n
    for i in range(n):
        for j in range(n):
            if i != j:
                exclusiveA[i] = combine(exclusiveA[i], A[j], node, j)
    return exclusiveA

def treeDP(root, graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
  DP = [0] * len(graph)
  def dfs(node, parent=-1):
    nodeDP = default[node]
    for eind, nei in enumerate(graph[node]):
      if nei != parent:
        neiDP = dfs(nei, node)
        nodeDP = combine(nodeDP, neiDP, node, eind)
    parent_eind = -1 if parent == -1 else graph[node].index(parent)
    DP[node] = finalize(nodeDP, node, parent_eind)
    return DP[node]
  
  dfs(root)
  return DP

def rerooter(graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
    n = len(graph)
    rootDP = [0] * n
    forwardDP = [None] * n
    reverseDP = [None] * n
 
    # Compute DP for root=0
    DP = treeDP(0, graph, default, combine, finalize)
     
    # Do rerooting using the exclusive function
    def dfs(node, parent=-1, parent_eind=-1):
        forwardDP[node] = [DP[nei] for nei in graph[node]]
        rerootDP = exclusive(forwardDP[node], default[node], combine, node)
        reverseDP[node] = [finalize(nodeDP, node, eind) for eind, nodeDP in enumerate(rerootDP)]
        nodeDP = combine(rerootDP[0], forwardDP[node][0], node, 0) if n > 1 else default[node]
        rootDP[node] = finalize(nodeDP, node, -1)
        for eind, nei in enumerate(graph[node]):
            if nei != parent:
                DP[node] = reverseDP[node][eind]
                dfs(nei, node, eind)
    dfs(0)
    return rootDP, forwardDP, reverseDP

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)

def exclusive(A, zero, combine, node):
    n = len(A)
    exclusiveA = [zero] * n # Exclusive segment tree
 
    # Build exclusive segment tree
    for bit in range(n.bit_length())[::-1]:
        for i in range(n)[::-1]:
            # Propagate values down the segment tree    
            exclusiveA[i] = exclusiveA[i // 2]
        for i in range(n & ~(bit == 0)):
            # Fold A[i] into exclusive segment tree
            ind = (i >> bit) ^ 1
            exclusiveA[ind] = combine(exclusiveA[ind], A[i], node, i)
    return exclusiveA

def treeDP(root, graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
  DP = [0] * len(graph)
  def dfs(node, parent=-1):
    nodeDP = default[node]
    for eind, nei in enumerate(graph[node]):
      if nei != parent:
        neiDP = dfs(nei, node)
        nodeDP = combine(nodeDP, neiDP, node, eind)
    parent_eind = -1 if parent == -1 else graph[node].index(parent)
    DP[node] = finalize(nodeDP, node, parent_eind)
    return DP[node]
  
  dfs(root)
  return DP

def rerooter(graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
    n = len(graph)
    rootDP = [0] * n
    forwardDP = [None] * n
    reverseDP = [None] * n
 
    # Compute DP for root=0
    DP = treeDP(0, graph, default, combine, finalize)
     
    # Do rerooting using the exclusive function
    def dfs(node, parent=-1, parent_eind=-1):
        forwardDP[node] = [DP[nei] for nei in graph[node]]
        rerootDP = exclusive(forwardDP[node], default[node], combine, node)
        reverseDP[node] = [finalize(nodeDP, node, eind) for eind, nodeDP in enumerate(rerootDP)]
        nodeDP = combine(rerootDP[0], forwardDP[node][0], node, 0) if n > 1 else default[node]
        rootDP[node] = finalize(nodeDP, node, -1)
        for eind, nei in enumerate(graph[node]):
            if nei != parent:
                DP[node] = reverseDP[node][eind]
                dfs(nei, node, eind)
    dfs(0)
    return rootDP, forwardDP, reverseDP

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)

def exclusive(A, zero, combine, node):
    n = len(A)
    exclusiveA = [zero] * n # Exclusive segment tree
 
    # Build exclusive segment tree
    for bit in range(n.bit_length())[::-1]:
        for i in range(n)[::-1]:
            # Propagate values down the segment tree    
            exclusiveA[i] = exclusiveA[i // 2]
        for i in range(n & ~(bit == 0)):
            # Fold A[i] into exclusive segment tree
            ind = (i >> bit) ^ 1
            exclusiveA[ind] = combine(exclusiveA[ind], A[i], node, i)
    return exclusiveA
 
def rerooter(graph, default, combine, finalize = lambda nodeDP,node,eind: nodeDP):
    n = len(graph)
    rootDP = [0] * n
    forwardDP = [None] * n
    reverseDP = [None] * n
 
    # Compute DP for root=0
    DP = [0] * n
    bfs = [0]
    P = [0] * n
    for node in bfs:
        for nei in graph[node]:
            if P[node] != nei:
                P[nei] = node
                bfs.append(nei)
 
    for node in reversed(bfs):
        nodeDP = default[node]
        for eind, nei in enumerate(graph[node]):
            if P[node] != nei:
                nodeDP = combine(nodeDP, DP[nei], node, eind)
        DP[node] = finalize(nodeDP, node, graph[node].index(P[node]) if node else -1)
    # DP for root=0 done
    
    # Use the exclusive function to reroot 
    for node in bfs:
        DP[P[node]] = DP[node]
        forwardDP[node] = [DP[nei] for nei in graph[node]]
        rerootDP = exclusive(forwardDP[node], default[node], combine, node)
        reverseDP[node] = [finalize(nodeDP, node, eind) for eind, nodeDP in enumerate(rerootDP)]
        rootDP[node] = finalize((combine(rerootDP[0], forwardDP[node][0], node, 0) if n > 1 else default[node]), node, -1)
        for nei, dp in zip(graph[node], reverseDP[node]):
            DP[nei] = dp
    return rootDP, forwardDP, reverseDP

Rev.	By	When	Δ	Comment
en9	pajenegod	2024-01-25 14:18:13	2762	Made list of problems more fancy
en8	pajenegod	2024-01-18 11:21:57	475	Added more reroot problems + solutions to the list
en7	pajenegod	2024-01-04 02:37:58	79
en6	pajenegod	2024-01-03 23:10:35	10	Tiny change: 'ssion:240129139]\n\n<spoi' -> 'ssion:240150867]\n\n<spoi'
en5	pajenegod	2024-01-03 22:31:04	6	Tiny change: 'deDP, node):\n retu' -> 'deDP, node, eind):\n retu'
en4	pajenegod	2024-01-03 22:30:20	20
en3	pajenegod	2024-01-03 22:28:31	12
en2	pajenegod	2024-01-03 22:25:55	83
en1	pajenegod	2024-01-03 22:18:54	18384	Initial revision (published)