7-6 有趣的最近公共祖先问题 倍增

给出一颗二叉树的后序遍历和中序遍历，你能计算出两个结点的最近公共祖先吗？
输入格式:

第一行给出两个整数N(N<=10000)和M(M<=10000)，分别代表二叉树的结点数和我们接下来的询问数。

第二行和第三行分别给出N个整数，每个整数用空格分开，分别代表二叉树的后序遍历和中序遍历。

接下来M行，每行给出两个整数，代表我们要询问的两个结点的编号a和b。
输出格式:

对于每个我们要求的询问：

1.如果a和b中有一个或两个不在树上，输出"ERROR"。

2.否则在一行中输出一个整数，表示a和b的最近公共祖先。
输入样例:

在这里给出一组输入。例如：

3 3
2 3 1
2 1 3
1 2
2 3
0 3

输出样例:

在这里给出相应的输出。例如：

1
1
ERROR

我的代码过于繁琐,不推荐阅读

$我们可以倍增求LCA(不是正解,正解不会)$我们可以倍增求LCA(不是正解,正解不会)
先通过后序遍历和中序遍历重建二叉树,再倍增求就好了

#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K, aft[MAXN], ino[MAXN];
struct Node {
	Node *lef, *rig;
	int val;
	Node(int _val=0) : lef(0), rig(0), val(_val) { }
} *root;

#if 0
Node* build(int al, int ar, int il, int ir) {
	Node* ret = new Node(aft[ar]);
	if(al == ar) return ret;
	for(int i=il, cnt=0; i<=ir; i++, cnt++)
		if(ret->val == ino[i]) {
			ret->lef = build(al, al+cnt, il, i-1);
			ret->rig = build(al+cnt+1, ar, il+1, ir);
		}
	return ret;
}
#else 
//重建二叉树
Node* build(int il, int ir, int al, int ar) {
	Node* ro = 0;
	if(il > ir) return ro;
	if(il == ir) 
      return (ro = new Node(aft[ar]));
	ro = new Node(aft[ar]);
	for(int i=il, cnt=0; i<=ir; i++) {
		if(ino[i] == ro->val) {
			ro->lef = build(il, i-1, al, al+cnt-1);
			ro->rig = build(i+1, ir, al+cnt, ar-1);
			break;
		}
		cnt ++;
	}
	return ro;
}
#endif

vector<int> G[MAXN];
int up[MAXN][25], dep[MAXN];

void toG(Node* now, int fa) { //把指针的树转化成邻接表存法 多此一举但符合我的习惯
	if(now) {
		G[now->val].push_back(fa);
		G[fa].push_back(now->val);
		toG(now->lef, now->val);
		toG(now->rig, now->val);
	}
}

void dfs(int u, int fa) { //dfs预处理
	dep[u] = dep[fa] + 1;
	up[u][0] = fa; //从u向上条2^0=1步是父节点fa
	//向上2^1, 2^2, 2^3, 2^4步(利用公式2^j = 2^(j-1) + 2^(j-1))
	for(int i=1; (1<<i)<=dep[u]; i++) 
		up[u][i] = up[up[u][i-1]][i-1];
	for(auto v : G[u])
		if(v != fa) dfs(v, u);
}
int lca(int u, int v) {
	//保证u在上面
	if(dep[u] > dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) //v向上跳到和u同层 
		if(dep[u] <= dep[v]-(1<<i))
			v = up[v][i];
	if(u == v) return u;
	for(int i=20; i>=0; i--) //一起同时跳
		if(up[u][i] == up[v][i]) //向上2^i步是相同,说明i可以更小
			continue ;
		else { //向上2^i步不相同,说明要往上条2^i步
			u = up[u][i];
			v = up[v][i];
		}
	return up[u][0]; //返回u的父节点就是lca
}

void preo(Node* now) {
	if(now) {
		printf("%d ", now->val);
		preo(now->lef);
		preo(now->rig);
	}
}

void inor(Node* now) {
	if(now) {
		preo(now->lef);
		printf("%d ", now->val);
		preo(now->rig);
	}
}

void afto(Node* now) {
	if(now) {
		preo(now->lef);
		preo(now->rig);
		printf("%d ", now->val);
	}
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(n, m);
	set<int> seta;
	for(int i=1; i<=n; i++) read(aft[i]), seta.insert(aft[i]);
	for(int i=1; i<=n; i++) read(ino[i]);
	root = build(1, n, 1, n);
	toG(root, root->val);
	int u, v;
	dfs(1, 0);
	while(m--) {
		read(u, v);
		if(seta.find(u)!=seta.end() && seta.find(v)!=seta.end()) {
			printf("%d\n", lca(u, v));
		} else {
			printf("ERROR\n");
		}
	}


#ifdef debug
	clock_t etime = clock();
// printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}