Sign in to watch this lesson
Advanced - Trees Ā· 3:56
Painting Tree Edges (Euler-Tour Edge Trick)
Write an edge into a tour every time a depth-first walk goes down it and again when it comes back up, so each edge appears exactly twice. Between pos[a] and pos[j] for an ancestor a of j, every side trip appears as a matched down-up pair and cancels, leaving exactly the path's edges going down; two Fenwick trees (painted down tabs and painted up tabs) count painted edges on the path as a difference. A general path splits at the LCA, and painting or unpainting an edge updates both trees, all in O(log n).
You will learn
- Build the edge tour with one iterative DFS, recording each edge's down and up positions and pos[v] for every vertex
- Explain why side trips cancel in [pos[a], pos[j]) and count painted path edges as T1 - T2 with two Fenwick trees
- Answer a general path by splitting at the LCA, and update both trees whenever an edge is painted or unpainted
- Avoid the off-by-one at pos[j] and recognise the trick as the same cancellation as subtree raises with +x/-x