Pseudocode
void change_root(int old_root, int new_root) {
// Update data structures as if `new_root` was being removed as a child from `old_root`
// Update data structures as if `old_root` was being added as a child to `new_root`
}
void walk(int vertex, int parent) {
// Data structures now reflect the tree as if `vertex` were the root
for (child in adjacency_list[vertex]) {
if (child == parent) continue;
change_root(vertex, child);
walk(child, vertex);
change_root(child, vertex);
}
}
// Initialize data structures with respect to the initial root `root`
walk(root, -1);
Problems
