Graph Theory37 sections · 1633 units
Open in Course

CSES 1674 Subordinates - Core Idea

Subtree size minus one

The number of subordinates of node vv is the size of the subtree rooted at vv, minus 11 (do not count vv itself). Define ext{size}[v] = number of nodes in subtree of vv (including vv itself). Then subordinates[v] = ext{size}[v] - 1.

This converts the problem into a standard subtree aggregation: compute sizes, then subtract one. This is a common pattern. When the problem asks for something slightly different from what you compute, adjust at the end.