Finding a centroid takes time for a tree with nodes. The recursion has depth because each level halves component sizes. Each node appears in recursive calls. Processing paths through a centroid takes time for that subtree.
Since each node is processed times across all levels, total time is . Overall: for building the decomposition and solving path problems. Space is for the tree and auxiliary arrays.
Space complexity is for the data structures used.