Graph Theory37 sections · 1633 units
Open in Course

Rerooting Limitation

(Fixed root only)

Euler tour assumes a fixed root. If you reroot the tree, all tintin and touttout values change. For problems requiring different roots, either recompute the Euler tour each time (slow) or use rerooting DP to adjust answers without recomputing.

Euler tour and rerooting solve different problem classes. Do not mix them unless you have a specific reason. Rerooting DP runs in O(n)O(n) and computes answers for all possible roots without rebuilding any data structures.