AcWing 3555. 二叉树

https://www.acwing.com/problem/content/description/3558/

输入样例：
1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1
输出样例：
2
4
2
4

详解见代码内部

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
int n,m;
int father[N],L[N],R[N];
int find(int x,int a[])//从x这个点开始往上搜索父节点，并且存储在相应的数组中
{
    int res=0;//下标从0开始
    while(x!=1)//没有到达根节点
    {
        a[res++]=x;//离得更近的父节点装进去（注意自己也装进去了）
        x=father[x];//找父节点的父节点，依次往上递增寻找
    }
    a[res++]=1;//最后把根节点装进去
    return res;//返回这一条路的父节点们
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            LL x,y;
            cin>>x>>y;
            //有子节点，则记录
            if(x!=-1) father[x]=i;
            if(y!=-1) father[y]=i;
        }
        while(m--)
        {
            LL l,r;
            cin>>l>>r;
            //sum表示父节点的个数
            LL suml=find(l,L);//L储存所有l父节点的信息
            LL sumr=find(r,R);//R储存所有r父节点的信息
            //下标是从0开始的，所以倒过来-1
            //这里是从头开始往更深的地方寻找
            for(int i=suml-1,j=sumr-1;i>=0&&j>=0;i--,j--)
            {
                if(L[i]==R[j])//这里还一样的话，说明还可以在向下探索一下
                {
                    //此处有标记
                    suml--;
                    sumr--;
                }
                else break;//这里已经不一样了，直接退出
            }
            cout<<suml+sumr<<endl;
        }
    }
    return 0;
}