AlgoWiki

Tree walk trick

    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