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

$ curl repovive.com/roadmaps/graph-theory/rerooting-technique/final-answer-combining-down-and-up

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

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

$ curl repovive.com/roadmaps/graph-theory/rerooting-technique/final-answer-combining-down-and-up

Repovive

Final Answer (Combining down and up) - Rerooting Technique | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Final Answer (Combining down and up)

(Merge down and up)

For each node $v$ , the final answer combines two pieces of information.

The down contribution is what you computed when $v$ was in a subtree during Phase $1$ . This captures everything below $v$ .

The up contribution is what comes from the rest of the tree when $v$ acts as the root during Phase $2$ . This captures everything above $v$ .

For tree diameter, the answer at node $v$ is the maximum depth you can reach going down into any subtree OR going up through the parent and then down into sibling subtrees.

answer[v] := max(dp_down[v], dp_up[v])

This gives you every node's "view" of the tree. You compute all $n$ answers in $O(n)$ total time instead of running $n$ separate DFS traversals. That is the power of rerooting: you reuse information instead of recomputing it.

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