1143 Lowest Common Ancestor

Two points timeout, there is no choice to build the tree first, may lead to too much recursion, so timeout, code:

#include<iostream>
#include<set>
#include<vector>
using namespace std;
set<int> se;
int a[10010];
int b[10010];
int n1,n2;
set<int> father;
vector<int> v;
bool f1=false,f2=false;
void func1(int l1,int r1,int l2,int r2,int aim,int t2){
    int t=l2;
    for(t;t<=r2&&b[t]!=a[l1];t++);
    if(aim<b[t]){
        if(b[t]==t2){f1=true;return;}
        father.insert(b[t]);
        func1(l1+1,t-l2+l1,l2,t-1,aim,t2);
    }
    else if(aim>b[t]){
        if(b[t]==t2){f1=true;return;}
        father.insert(b[t]);
        func1(l1+t-l2+1,r1,t+1,r2,aim,t2);
    }
    return;
}
void func2(int l1,int r1,int l2,int r2,int aim,int t1){
    int t=l2;
    for(t;t<=r2&&b[t]!=a[l1];t++);
    if(aim<b[t]){
        if(b[t]==t1){f2=true;return;}
        v.push_back(b[t]);
        func2(l1+1,t-l2+l1,l2,t-1,aim,t1);
    }
    else if(aim>b[t]){
        if(b[t]==t1){f2=true;return;}
        v.push_back(b[t]);
        func2(l1+t-l2+1,r1,t+1,r2,aim,t1);
    }
    return;
}
int main(){
    cin>>n1>>n2;
    for(int i=0;i<n2;i++){
        cin>>a[i];
        se.insert(a[i]);
    }
    auto it=se.begin();
    for(int i=0;i<n2;i++){
        b[i]=*it;
        it++;
    }
    for(int i=0;i<n1;i++){
        f1=false;f2=false;
        int t1,t2;
        cin>>t1>>t2;
        
        if(se.find(t1)==se.end()&&se.find(t2)==se.end()){
            cout<<"ERROR: "<<t1<<" and "<<t2<<" are not found."<<endl;
            continue;
        }
        else if(se.find(t1)==se.end()&&se.find(t2)!=se.end()){
            cout<<"ERROR: "<<t1<<" is not found."<<endl;
            continue;
        }
        else if(se.find(t1)!=se.end()&&se.find(t2)==se.end()){
            cout<<"ERROR: "<<t2<<" is not found."<<endl;
            continue;
        }
        if(t1==t2){
            cout<<t1<<" is an ancestor of "<<t1<<"."<<endl;
            continue;
        }
        father.clear();
        v.clear();
        father.insert(a[0]);
        v.push_back(a[0]);
        func1(0,n2-1,0,n2-1,t1,t2);
        if(f1){
            cout<<t2<<" is an ancestor of "<<t1<<"."<<endl;
            continue;
        }
        func2(0,n2-1,0,n2-1,t2,t1);
        if(f2){
            cout<<t1<<" is an ancestor of "<<t2<<"."<<endl;
            continue;
        }
        for(int i=v.size()-1;i>=0;i--){
            if(father.find(v[i])!=father.end()){
                cout<<"LCA of "<<t1<<" and "<<t2<<" is "<<v[i]<<"."<<endl;
                break;
            }
        }
    }
    return 0;
}


Read More: