Graph Theory37 sections · 1633 units
Open in Course

Core Idea - Which Times to Use

(Entry times only)

You need one position per node in your array. Use entry times: arr[tin[v]] = value[v]. Subtree of vv spans positions tin[v] to tout[v] in this array.

But tout[v] does not hold a node value. The range is [tin[v], tout[v]] but only positions with nodes (entry times) contribute to the sum. Since entry times are consecutive (0,1,2,.,n10, 1, 2,., n-1), the range query works correctly. Make sure your tout[v] boundary is inclusive or exclusive consistently throughout your code.