Graph Theory37 sections · 1633 units
Open in Course

Core Idea - Prefix Sum Trick

(Converting to range query)

Instead of storing node values, store cumulative sums. When entering node vv, add its value. When exiting, subtract its value. Now arr[tin[v]] holds +value[v] and arr[tout[v]] holds -value[v].

Path sum from root to vv = prefix sum from 00 to tin[v] in this array. This works because DFS enters all ancestors before vv and exits them after, so their contributions are counted exactly once.