本地测0.5s，交上去全TLE/MLE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<ctime>
#define int long long
const int maxn=1e5+5;
using namespace std;


int read() {
	int sum=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return f*sum;
}
int n,m,t,tim=1,flag;
int hd[maxn],f[maxn],fa[maxn][25],dep[maxn];
struct edge{
    int u,v,nxt;
}e[maxn<<1];
void dfs(int u,int fath){
    fa[u][0]=fath;
    dep[u]=dep[fath]+1;
    for(int i=hd[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fath)continue;
        dfs(v,u);
    }
}
void addedge(int u,int v){
    e[++t].u=u,e[t].v=v,e[t].nxt=hd[u],hd[u]=t;
}
void init(){
       f[2]=f[3]=1;
    for(int i=4;i<maxn;i++){
        f[i]=f[i-1]+f[i-2];
        if(f[i]>maxn){
            n=i;break;
        }
    } 
	printf("%d \n",n);       
    for(int i=2;i<=n;i++){
        for(int j=1;j<=f[i];j++){
            addedge(j,++tim);
            addedge(tim,j);
            if(tim>maxn){
            	flag=1;break;
            }            
                
        }
        if(flag)
            break;
    } 
    dfs(1,1);
    for(int j=1;j<=24;j++)
        for(int i=1;i<=maxn-3;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];

}
int lca(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=24;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y)return x;
    for(int i=24;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
signed main() {
	//freopen("P3938_1.in","r",stdin);
    //freopen("P3938.out","w",stdout);
    init();
    m=read();
    for(int i=1,u,v;i<=m;i++){
        u=read(),v=read();
        printf("%lld\n",lca(u,v));
    }
	return 0;
}