Implement Cache, Undo, and DFS

Problem Statement

You are building a metadata management system for a hierarchical organizational structure represented as a tree, where each node has a unique id and a value. Implement a system that supports three main operations: caching access to nodes, modifying values with undo capability, and performing a depth-first search (DFS) to retrieve a total aggregate value.

Requirements

1. LRU Cache: Maintain a cache of the most recently accessed nodes with a fixed capacity k. If the cache is full, evict the least recently used node.
2. Command Undo: Support an update(id, new_value) operation. Each update must be stored in a stack. An undo() operation should revert the most recent update to its previous state.
3. DFS Traversal: Implement a get_subtree_sum(root_id) function that returns the sum of values of the subtree rooted at root_id. This traversal must also cache each node's value as it visits it.

Interface

class OrgSystem:
    def __init__(self, nodes, capacity):
        # nodes is a dict: {id: (value, parent_id)}
        pass
        
    def get(self, id):
        # Returns value, updates cache, uses LRU eviction
        pass
        
    def update(self, id, new_value):
        # Updates value, pushes change to undo stack
        pass
        
    def undo(self):
        # Reverts the last update
        pass
        
    def get_subtree_sum(self, root_id):
        # Performs DFS, returns sum of subtree values
        pass

Constraints

• Number of nodes N <= 10^5.
• Cache capacity k is between 1 and N.
• Ensure undo operations are thread-safe or logically sound.

Example

Input: nodes = {1: (10, None), 2: (5, 1), 3: (3, 1)}, capacity = 2 get(2) -> returns 5 update(2, 20) -> value of 2 becomes 20 undo() -> value of 2 reverts to 5