题目链接

LCA核心

这几行代码简直优美到爆，比我看了一天的倍增和tarjan美观多了。

node* LCA(node* root, int u, int v){
	if(root == NULL) return NULL;
	if(root->x == u || root->x==v) return root;
	node* l = LCA(root->left, u, v);
	node* r = LCA(root->right, u, v);
	if(l != NULL && r != NULL) return root;
	return l==NULL?r:l; 
}

AC代码

还是要多刷题才是呀！

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
map<int, bool> mp;
int pre[maxn],in[maxn];
struct node{
	int x;
	node* left;
	node* right;
};
//离线建树好一点 
void create(node* &root, int preL, int preR, int inL, int inR){
	if(preL > preR ) return;
	root = new node; //很关键 
	root->x = pre[preL];
	root->left = root->right =NULL;
	int k=inL;
	while(in[k] != pre[preL]){
		k++;
	}
	int tmp = k - inL;
	create(root->left,preL+1, preL+tmp, inL, k-1);
	create(root->right,preL+tmp+1, preR, k+1, inR);
	
}

//深搜 
node* LCA(node* root, int u, int v){
	if(root == NULL) return NULL;
	if(root->x == u || root->x==v) return root;
	node* l = LCA(root->left, u, v);
	node* r = LCA(root->right, u, v);
	if(l != NULL && r != NULL) return root;
	return l==NULL?r:l; 
}

int main(){
	int n,m,x,y;
	node* root = NULL;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d",&x);
		in[i]=x;
		mp[x]=true;
	}
	for(int i=0;i<m;i++){
		scanf("%d",&x);
		pre[i]=x;
		mp[x]=true;
	}
	create(root,0, m-1, 0, m-1);

	for(int i=0;i<n;i++){
		scanf("%d%d",&x,&y);
		if(mp[x]==false && mp[y]==false) printf("ERROR: %d and %d are not found.\n", x, y);
		else if(mp[x]==false)  printf("ERROR: %d is not found.\n", x);
		else if(mp[y]==false)  printf("ERROR: %d is not found.\n", y);
		else{
			node* T = LCA(root, x, y);
			if(T->x == x || T->x == y)
				printf("%d is an ancestor of %d.\n",T->x==x?x:y,T->x==x?y:x);
			else
				printf("LCA of %d and %d is %d.\n",x,y,T->x);
		}	
	}
	return 0;
}