[Python] Simple traverse + DP, O(n)
The idea is simple, say a node A has left child B and right child C, max depth in the tree after removing C is either:\n\n              X\n       A            X
The idea is simple, say a node A has left child B and right child C, max depth in the tree after removing C is either:\n```\n              X\n       A            X\n    B     C      X     X\n   X X   X X \n```\n(1) the max depth within the sub tree of B, or \n(2) the max depth  in the tree after removing A\n\nmax_depth_without_subtree(val) returns max depth in the tree after removing subtree at node with value val. then (1) is done through recursion (with cache/dp to avoid re-computation) while (2) is done by simply storing every node\'s depth and max depth of its left/right sub tree in one pass by dfs(node, parent, depth).\n\ncomplexity is O(n) for 1 pass preprocessing and O(n + #queries) for max_depth_without_subtree(val) on all queries due to the cache, and eventually O(n) since #queries <= n.\n\n```\nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        node_to_parent = {}\n        value_to_node = {}\n        # node to its depth\n        node_to_depth = {}\n        # node to max depth of its left and right subtree\n        node_to_subtree_max_depths = {}\n        \n        def traverse(node, parent, depth):\n            if not node:\n                return 0\n            value_to_node[node.val] = node\n            node_to_parent[node] = parent\n            node_to_depth[node] = depth\n            l = dfs(node.left, node, depth+1)\n            r = dfs(node.right, node, depth+1)\n            node_to_subtree_max_depths[node] = [l, r]\n            return max(l, r)+1\n        \n        traverse(root, None, 0)\n        \n        @cache\n        def max_depth_without_subtree(val):\n            node = value_to_node[val]\n            if node == root:\n                return -1\n            parent = node_to_parent[node]\n            if parent.left == node:\n                max_depth = node_to_depth[parent] + node_to_subtree_max_depths[parent][1]\n            else:\n                max_depth = node_to_depth[parent] + node_to_subtree_max_depths[parent][0]\n            return max(max_depth, max_depth_without_subtree(parent.val))\n        \n        return [max_depth_without_subtree(q) for q in queries] \n```
[]