1143.md

1143

• 1143 Lowest Common Ancestor (30 point(s))

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int M, N;
const int MAX_M = 1e3 + 5;
const int MAX_N = 1e4 + 5;
struct Node {
	int v;
	Node* l;
	Node* r;
};
vector<int> preOrder, inOrder;

void build(Node*& root, int preL, int preR, int inL, int inR) {
	if (preL > preR || inL > inR) {
		return;
	}
	if (!root) {
		root = new Node();
		root->v = preOrder[preL];
		root->l = root->r = NULL;
	}
	int numLeft = find(inOrder.begin() + inL, inOrder.begin() + inR + 1, root->v) - inOrder.begin() - inL;
	build(root->l, preL + 1, preL + numLeft, inL, inL + numLeft - 1);
	build(root->r, preL + numLeft + 1, preR, inL + numLeft + 1, inR);
}

void in(Node* root) {
	if (!root) {
		return;
	}
	in(root->l);
	printf("%d ", root->v);
	in(root->r);
}

bool search(vector<int>& v, Node* root, int val) {
	if (!root) {
		return false;
	}
	v.push_back(root->v);
	if (root->v == val) {
		return true;
	}
	else if (val > root->v) {
		return search(v, root->r, val);
	}
	else {
		return search(v, root->l, val);
	}
}

int main() {
	scanf("%d %d", &M, &N);
	for (int n = 0; n < N; n++) {
		int x;
		scanf("%d", &x);
		preOrder.push_back(x);
	}
	inOrder = preOrder;
	sort(inOrder.begin(), inOrder.end());
	Node* root = NULL;
	build(root, 0, N - 1, 0, N - 1);
	// in(root);
	for (int m = 0; m < M; m++) {
		int A, B;
		scanf("%d %d", &A, &B);
		vector<int> a, b;
		bool flag1 = search(a, root, A), flag2 = search(b, root, B);
		if (flag1 && flag2) {
			int ancestor;
			for (int i = 0; i < min(a.size(), b.size()); i++) {
				if (a[i] == b[i]) {
					ancestor = a[i];
				}
				else {
					break;
				}
			}
			if (ancestor == A) {
				printf("%d is an ancestor of %d.\n", A, B);
			}
			else if (ancestor == B) {
				printf("%d is an ancestor of %d.\n", B, A);
			}
			else {
				printf("LCA of %d and %d is %d.\n", A, B, ancestor);
			}
		}
		else {
			if (!flag1 && flag2) {
				printf("ERROR: %d is not found.\n", A);
			}
			else if (flag1 && !flag2) {
				printf("ERROR: %d is not found.\n", B);
			}
			else if (!flag1 && !flag2) {
				printf("ERROR: %d and %d are not found.\n", A, B);
			}
		}
	}
	return 0;
}

/*
Sample Input:
6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.
*/

References