PAT-1151-LCA in a Binary Tree

1151

参考浒鱼鱼

//
// Created by ZhangXiaoYu@Ceres_lab on 2020/8/31.
//#include<iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>using namespace std;map<int,int> pos;
vector<int> in,pre;void lca(int l,int r,int preRoot,int a,int b){
    if(l>r)return;int inroot = pos[pre[preRoot]];if(pos[a]>inroot && pos[b]>inroot) //都在右边{
    lca(inroot+1,r,preRoot+1+inroot-l,a,b);}else if(pos[a]<inroot && pos[b]<inroot){
    lca(l,inroot-1,preRoot+1,a,b);}else if((pos[a]>inroot&& pos[b]<inroot) || (pos[a]<inroot && pos[b]>inroot)){
    printf("LCA of %d and %d is %d.\n",a,b,in[inroot]);}else if(pos[a]==inroot)printf("%d is an ancestor of %d.\n", a, b);else if(pos[b]==inroot) printf("%d is an ancestor of %d.\n",b,a);
}int main(){
    freopen("input.txt","r",stdin);int m,n;cin>>m>>n;in.resize(n+1);pre.resize(n+1);for(int i=1;i<=n;i++){
    scanf("%d",&in[i]);pos[in[i]]=i;}for(int i=1;i<=n;i++)scanf("%d",&pre[i]);int a,b;for(int i =0;i<m;i++){
    scanf("%d %d",&a,&b);if(pos[a]==0 && pos[b]==0)printf("ERROR: %d and %d are not found.\n", a, b);else if(pos[a] == 0 ||pos[b]==0){
    printf("ERROR: %d is not found.\n", pos[a] == 0 ? a : b);}else lca(1,n,1,a,b);}
// fclose(stdin);return 0;
}