<< 给个赞吧~

$\huge\color{Gold}{暑假每日一题2022}\color{black}{题解集合}$

算法

$\texttt{LCA}$

C++ 代码（带注释

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
int t;
int fa[1010110],l[1010011],r[1001110],d[1001101];
void dfs(int root,int dep){
    if(root==-1) return;     //为空就跳出
    d[root]=dep;     //把当前节点的深度设为dep
    dfs(l[root],dep+1);     //继续遍历左子树
    dfs(r[root],dep+1);     //继续遍历右子树
}
int search(int x,int y){
    while(d[x]>d[y]) x=fa[x];     //如果x的深度大于y的深度，就把x设为它的父节点（向上走）
    while(d[y]>d[x]) y=fa[y];     //如果y的深度大于x的深度，就把y设为它的父节点（向上走）
    while(x!=y) x=fa[x],y=fa[y];     //x不等于y的时候，两个节点一起向上走
    return x;     //返回x,y都行
}
int main(){
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            l[i]=x;     //设置当前节点的左子节点
            r[i]=y;     //设置当前节点的右子节点
            if(x!=-1) fa[x]=i;     //若不为空，就将它的父节点设为当前节点
            if(y!=-1) fa[y]=i;
        }
        dfs(1,1);     //遍历整棵树，设置节点的深度
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            printf("%d\n",d[x]+d[y]-2*d[search(x,y)]);
        }
    }
    return 0;
}

C++ 代码（无注释

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
int t;
int fa[1010110],l[1010011],r[1001110],d[1001101];
void dfs(int root,int dep){
    if(root==-1) return;
    d[root]=dep;
    dfs(l[root],dep+1);
    dfs(r[root],dep+1);
}
int search(int x,int y){
    while(d[x]>d[y]) x=fa[x];
    while(d[y]>d[x]) y=fa[y];
    while(x!=y) x=fa[x],y=fa[y];
    return x;
}
int main(){
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            l[i]=x;
            r[i]=y;
            if(x!=-1) fa[x]=i;
            if(y!=-1) fa[y]=i;
        }
        dfs(1,1);
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            printf("%d\n",d[x]+d[y]-2*d[search(x,y)]);
        }
    }
    return 0;
}