复习提高版

#include <iostream>
#include <climits>
#include <unordered_map>

using namespace std;

#define rep(inc, frm, to) for (int inc = frm; inc < (to); ++inc)

using ll = long long int;
#define r() fast_read()

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (not isdigit(c)) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (isdigit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

struct TNode {
  long parent, lchild, rchild;
  int depth;
  TNode() {
    parent = lchild = rchild = LONG_MIN; 
    depth = 0;
  }
};

int m, n;
unordered_map<int, TNode> tree;

long buildTree(int* in, int* pre, int n, int depth) {
  if (n <= 0) return LONG_MIN;
  int rt = *pre;
  tree[rt].depth = depth;
  if (n == 1) return rt;

  int index = -1;
  while (in[++index] != rt);
  tree[rt].lchild = buildTree(in, pre + 1, index, depth + 1);
  tree[rt].rchild = buildTree(in + index + 1, pre + 1 + index, n - 1 - index, depth + 1);
  long lch = tree[rt].lchild, rch = tree[rt].rchild;
  if (lch != LONG_MIN) tree[lch].parent = rt;
  if (rch != LONG_MIN) tree[rch].parent = rt;
  return rt;
}

int lowestCommonAncestor(int u, int v) {
  if (tree[u].depth < tree[v].depth) swap(u, v);
  while (tree[u].depth != tree[v].depth) u = tree[u].parent;
  while (u != v) {
    u = tree[u].parent;
    v = tree[v].parent;
  }
  return u;
}

bool exists(int u) {
  return tree.find(u) != end(tree);
}

signed main(int argc, char const *argv[]) {
  // freopen("test.in", "r", stdin);

  m = r(), n = r();
  int inorder[n], preorder[n];
  rep(i, 0, n) *(inorder + i) = r();
  rep(i, 0, n) *(preorder + i) = r();

  buildTree(inorder, preorder, n, 0);
  for (int u, v, lca; m--;) {
    u = r(), v = r();
    if (not(exists(u) and exists(v))) { // u和v不是两个都存在 (至少一个不存左或者两个都不存在)
      if (not(exists(u) or exists(v))) printf("ERROR: %d and %d are not found.\n", u, v); // u和v两个都不存左
      else if (not exists(u)) printf("ERROR: %d is not found.\n", u);
      else if (not exists(v)) printf("ERROR: %d is not found.\n", v);
      continue;
    }
    lca = lowestCommonAncestor(u, v);
    if (lca != u and lca != v) printf("LCA of %d and %d is %d.\n", u, v, lca);
    else if (lca == u or lca == v) {
      if (lca == u) printf("%d is an ancestor of %d.\n", u, v);
      else printf("%d is an ancestor of %d.\n", v, u);
    }
  }

  // fclose(stdin);
  return ~~(0 ^ 0);
}

我终于知道为什么程序员叫码农了。。。 全是脑力体力啊！

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#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* buildTree(vector<int>& preorder, vector<int>& inorder) {

  unordered_map<int, int> indices;
  for (int i = 0; i < inorder.size(); ++i)
    indices[inorder[i]] = i;

  function<TreeNode*(int, int, int)> construct = [&](int i, int j , int n) {
    // recursion exit condition (base case)
    if (n <= 0) return (TreeNode*) nullptr;
    auto root = new TreeNode(preorder[i]);
    if (n == 1) // leaf node without children
      return root;

    int k = indices[preorder[i]];
    int l = k - j; // the length of the left subtree.

    root->left  = construct(i + 1, j, l);
    root->right = construct(i + 1 + l, k + 1, n - l - 1);
    return root;
  };

  return construct(0, 0, preorder.size());
}

TreeNode* lowestCommonAncestor(TreeNode* root, const int p, const int q) {
  if (!root || root->val == p || root->val == q) return root;
  const auto l = lowestCommonAncestor(root->left, p, q);
  const auto r = lowestCommonAncestor(root->right, p, q);
  return l && r ? root : l ? l : r;
}

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

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

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

  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;
    }

    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);
  }
}