[Segment Tree][C++][Euler Path] Explained
Run a euler tour on the tree to find the start time and end time of each node.\nStore the depth of each node in it\'s start time. \nBuild a Segment Tree contain
Run a euler tour on the tree to find the start time and end time of each node.\nStore the depth of each node in it\'s start time. \nBuild a Segment Tree containing the maximum of ranges.\nNow for each query  node <b>\'x\'</b> then answer will be the  maximum of the maximum of range\n<b>(1, start[x]-1)</b> and <b>(end[x]+1,totalTime)</b>.\n\nSample Code:\n```\nstruct SegmentTree {\n#define lc (C << 1)\n#define rc (C << 1 | 1)\n#define M ((L+R)>>1)\n  struct data {\n    int sum;\n    data() :sum(0) {};\n  };\n  vector<data>st;\n  int N;\n  SegmentTree(int _N) :N(_N) {\n    st.resize(4 * N);\n  }\n  void combine(data& cur, data& l, data& r) {\n    cur.sum = max(l.sum,r.sum);\n  }\n  data Query(int i, int j, int C, int L, int R) {\n    if (j < L || i > R || L > R) return data();\n    if (i <= L && R <= j) return st[C];\n    data ret;\n    data d1 = Query(i, j, lc, L, M);\n    data d2 = Query(i, j, rc, M + 1, R);\n    combine(ret, d1, d2);\n    return ret;\n  }\n  void Update(int i, int j, int val, int C, int L, int R) {\n    if (j < L || i > R || L > R) return;\n    if (i <= L && R <= j) {\n      st[C].sum = val;\n      return;\n    }\n    Update(i, j, val, lc, L, M);\n    Update(i, j, val, rc, M + 1, R);\n    combine(st[C], st[lc], st[rc]);\n  }\n  void Update(int i, int j, int val) {\n    Update(i, j, val, 1, 1, N);\n  }\n  int Query(int i, int j) {\n    return Query(i, j, 1, 1, N).sum;\n  }\n};\nclass Solution {\npublic: \n    int startTime[100001],endTime[100001];\n    int arr[100001];\n    int T;\n    void dfs(TreeNode* root,int d){\n        ++T;\n        startTime[root->val] = T;\n        arr[T] = d;\n        if(root->left!=nullptr)dfs(root->left,d+1);\n        if(root->right!=nullptr) dfs(root->right,d+1);\n        endTime[root->val] = T;\n    }\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        T = 0;\n        dfs(root,0);\n        SegmentTree st(T);\n        for(int i=1;i<=T;i++){\n            st.Update(i,i,arr[i]);\n        }\n        vector<int>ret;\n        for(int&x:queries){\n            int from = startTime[x];\n            int till = endTime[x];\n            int a = st.Query(1,from-1);\n            int b = st.Query(till+1,T);\n            ret.push_back(max(a,b));\n        }\n        return ret;\n    }\n};\n```
['Tree', 'C']