BST 建树和求LCA！

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>

using namespace std;
int m, n, u, v;

struct TreeNode {
  int val;
  TreeNode *left, *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

TreeNode* bstFromPreorder(vector<int>& preorder) {
  stack<TreeNode*> s;
  TreeNode *root = nullptr, *pnode = nullptr;

  for (const auto& val : preorder) {
    auto node = new TreeNode(val);
    if (s.empty()) {
      root = node;
    } else if (node->val < s.top()->val)
      s.top()->left = node;
    else {
      while (not s.empty() && node->val > s.top()->val) {
        pnode = s.top();
        s.pop();
      }
      pnode->right = node;
    }
    s.emplace(node);
  }

  return root;
}

TreeNode* lowestCommonAncestor(TreeNode* root, const int p, const int q) {
  if (!root) return nullptr;
  if (p < root->val && q < root->val)
    return lowestCommonAncestor(root->left, p, q);
  if (p > root->val && q > root->val)
    return lowestCommonAncestor(root->right, p, q);
  return root;
}

int main(void) {
  scanf("%d %d", &m, &n);

  vector<int> preorder(n);
  for (int i = 0; i < n; ++i) cin >> preorder[i];

  unordered_set<int> s(begin(preorder), end(preorder));
  auto root = bstFromPreorder(preorder);

  while (m--) {
    scanf("%d %d", &u, &v);
    if (!s.count(u) or !s.count(v)) {
      if (!s.count(u) and !s.count(v)) printf("ERROR: %d and %d are not found.\n", u, v);
      else if (!s.count(u))            printf("ERROR: %d is not found.\n", u);
      else                             printf("ERROR: %d is not found.\n", v);                
      continue;
    }
    if (u == v) { 
      printf("%d is an ancestor of %d.\n", u, v); 
      continue; 
    }

    int lca = lowestCommonAncestor(root, u, v)->val;
    if (lca != u && lca != v) printf("LCA of %d and %d is %d.\n", u, v, lca);
    else if (lca == u)        printf("%d is an ancestor of %d.\n", u, v);
    else                      printf("%d is an ancestor of %d.\n", v, u);
  }
}