#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/subtree-dp/subordinates-algorithm

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/subtree-dp/subordinates-algorithm

Repovive

CSES 1674 Subordinates - Algorithm - Subtree DP | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

CSES 1674 Subordinates - Algorithm

Single DFS pass

Run DFS from root (node $1$ ). For each node, visit children first, then compute subtree size.

function dfs(u, parent)
    size[u] := 1
    for each child v of u
        if v != parent then
            dfs(v, u)
            size[u] := size[u] + size[v]

After DFS, subordinates[u] = size[u] - 1 (subtract the node itself). This runs in $O(n)$ time, visiting each node once. The subtree size is a building block for many tree DP problems.

Space complexity is $O(n)$ for the data structures used.