lca疑似dfs栈溢出，求条（已解决）

常规
1

题目：

image
image746×371 18.3 KB

damn码

#include<bits/stdc++.h>
using namespace std;
#define int long long
 int n,m,x,fa[70][40010],h[40010],ct=0,d,ln;
 vector<int>vr[40010];
 map<int,int>mp;
int findd(int s){
    if(s==-1)return -1;
    if(mp.count(s)==0)mp[s]=++ct;
    return mp[s];
}
void dfs(int p,int f){
    for(int i=1;(1<<i)<=h[p];i++)fa[i][p]=fa[i-1][fa[i-1][p]];
    for(auto l:vr[p]){
        if(l!=f){
            fa[0][l]=p;
            h[l]=h[p]+1;
            dfs(l,p);
        }
    }
}
int lca(int a,int b){
    if(h[a]!=h[b]){
        if(h[a]<h[b])swap(a,b);
        d=h[a]-h[b];
        for(int i=0;(1<<i)<=d;i++)if((1<<i)&d)a=fa[i][a];
    }
    if(a==b)return a;
    for(int i=ln;i>=0;i--){
        if(fa[i][a]==fa[i][b])continue;
        a=fa[i][a];
        b=fa[i][b];
    }
    return fa[0][a];
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,u,v;i<=n;i++){
        cin>>u>>v;
        u=findd(u);
        v=findd(v);
        if(u!=-1)vr[u].push_back(v);
        else x=v;
        if(v!=-1)vr[v].push_back(u);
        else x=u;
    }
    h[x]=1;
    fa[0][x]=x;
    dfs(x,x);
    for(ln=60;(1<<ln)>n;ln--);
    cin>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b;
        a=mp[a];
        b=mp[b];
        c=lca(a,b);
        if(c==a)cout<<"1\n";
        else if(c==b)cout<<"2\n";
        else cout<<"0\n";
    }
	return 0;
}
/*

      ┏┛ ┻━━━━━┛ ┻┓
      ┃     ━     ┃
      ┃  ┳┛   ┗┳  ┃
      ┃           ┃
      ┃     ┻     ┃
      ┗━┓     ┏━━━┛
        ┃     ┃   神兽祝福
        ┃     ┃   草泥马祝你通关！
        ┃     ┗━━━━━━━━━┓
        ┃                ┣┓
        ┃                ┏┛
        ┗━┓ ┓ ┏━━━┳ ┓ ┏━┛
          ┃ ┫ ┫   ┃ ┫ ┫
          ┗━┻━┛   ┗━┻━┛
*/

样例：
输入：
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
输出：
1
0
0
0
2

本地运行都没问题，交上去要么RE要么TLE，0分，改了快一星期了，求条

3