Very Stupid C++ Solution (Eulerian Tour on Trees)
Warning\nThis is definitely not the most optimal solution, not just in time/memory complexity (both O(NlogN)), but also in implementation (as you can see below,
# Warning\nThis is definitely not the most optimal solution, not just in time/memory complexity (both O(NlogN)), but also in implementation (as you can see below, it isnt pretty, but I tried to explain it). \nI used the Euler tour technique on trees, which seems and likely is overkill\n\n \n# Algorithm\nNow, what the Euler tour technique does on a tree is flatten it into an array. Converting that array into a segtree, you can efficiently make queries on subtrees. \n\nI won\'t go into detail but essentially you order the array indexes (node # -> array index) by the order nodes are visited in a simple dfs. Therefore, for every subtree in the tree, each element in that subtree will lie in a continuous subsegment. (Draw a few examples and try it out).\n\nNext, you would make that array into a segtree, so you can query and modfiy values on the array. \n*In this case, those values are the max depth within the subtree we are querying, and since we arent modfiying, even an RMQ would suffice.\nhttps://usaco.guide/CPH.pdf#page=174 \nThis is a nice resource for learning this algorithm, as it becomes trivial for some advanced graph problems. \n\n# Intuition \nThe question is asking us what is the deepest node that is not in the subtree we are querying. Notice that there is only a left and a right we have to query (find the max from), and also notice if you compress the tree into an array, then the nodes that we may get the answer from will lie either to the left or right (or both) from the subsegment that represents the subtree we removed.\n\nWe will flatten our tree into an array/RMQ/segtree, and process each query in O(logN)\n\n\nWith a clear idea of our algorithm, the challenge now lies in implementation.\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\n\nint mxn = 1e5 + 5; \nint n, timer = 0; \nvector<vector<int>> adj(mxn); \nvector<int> st(mxn), en(mxn), d(mxn), to(mxn); \n//to[x] = time x is processed (order) in the dfs, index in the array\n//set the timer and compute st[x], en[x] = starting index\n//and ending index of the subtree with head of x\nvoid dfs(int node, int parent) {\n    st[to[node]] = timer++;\n    for (int i : adj[node]) {\n        if (i != parent) {\n            dfs(i, node);\n        }\n    }\n    en[to[node]] = timer-1;\n}\n\n//converting each node to the array index\nvoid make(TreeNode* x, int depth) {\n    to[x -> val - 1] = n; \n    n++; \n    d[to[x -> val - 1]] = depth; \n    \n    if (x -> right) {\n        make(x -> right, depth + 1); \n    } if (x -> left) {\n        make(x -> left, depth + 1); \n    }\n}\n\n//creating the adjacency list for the dfs \n//This is redundant, you could combine the dfs into this \n//recursive function to make it more elegant\nvoid make2(TreeNode* x) {\n    if (x -> right) {\n        adj[x -> val - 1].push_back(x -> right -> val - 1);\n        make2(x -> right); \n    } if (x -> left) {\n        adj[x -> val - 1].push_back(x -> left -> val - 1);\n        make2(x -> left); \n    }\n}\n\n//This is your classical segtree \n//Segtree: initialize, make, build, modify, query; \ntemplate <class T> \nclass St {\n    private: \n    vector<T> t;\n    int tn; T def = 0; \n    //operation and initial value\n    T op(T a, T b) {\n        return max(a, b); \n    } \n    public:\n    St(T N) { \n        t = vector<T>(2 * N, 0); \n        tn = N; \n    }\n\n    void make(vector<T> & a) { \n        for (int i = 0; i < tn; ++i) t[n+i] = a[i]; \n    } \n\n    void build() {\n        for (int i = tn - 1; i > 0; --i) t[i] = op(t[i<<1], t[i<<1|1]);\n    }\n\n    void modify(int p, T val) {\n        for (t[p += tn] = val; p > 1; p >>= 1) t[p>>1] = op(t[p], t[p^1]);\n    }\n\n    //query on [l, r)\n    T query(int l, int r) {  \n        T res = def;\n        for (l += tn, r += tn; l < r; l >>= 1, r >>= 1) {\n            if (l&1) res = op(res, t[l++]);\n            if (r&1) res = op(res, t[--r]);\n        }\n        return res;\n    }\n};\n\nclass Solution {\npublic:\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        //initialize and prepare for making segtree\n        n = 0; \n        timer = 0; \n        make(root, 0);\n        for (int i = 0; i < n; ++i) {\n            adj[i].clear();\n        }\n        //compress into array\n        make2(root); \n        dfs(root -> val - 1, -1); \n        \n        //make segtree\n        St s(n); \n        vector<int> vd(n); \n        for (int i = 0; i < n; ++i) {\n            vd[i] = d[i];\n        }\n        s.make(vd);\n        s.build(); \n        \n        vector<int> ans; \n\n        //process online queries\n        for (int i = 0; i < queries.size(); ++i) {\n            int x = queries[i]; \n            x--; \n            int mx = 0; \n            //if the left of the removed subtree exists, maximise the depth from the [0, left)\n            if (st[to[x]] > 0) {\n                mx = max(mx, s.query(0, st[to[x]])); \n            } \n            //if the right of the removed subtree exists, maximise the depth from the (right, n)\n            if (en[to[x]] < n - 1) {\n                mx = max(mx, s.query(en[to[x]] + 1, n));\n            }\n            ans.push_back(mx); \n        }\n         \n        return ans; \n    }\n};\n```
['C++']