acwing3555. 二叉树

题目

给定一个 n 个结点（编号 1∼n）构成的二叉树，其根结点为 1号点。

进行 m次询问，每次询问两个结点之间的最短路径长度。

树中所有边长均为 1。

题解

• 最短公共祖先

#include<iostream>
using namespace std;
const int N=1010;
int p[N],L[N],R[N];
int n,m,t;
int find(int x,int a[]){
    int k=0;
    while(x!=1){
        a[k++]=x;
        x=p[x];
    }
    return k;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            int a,b;
            cin>>a>>b;
            if(a!=-1)p[a]=i;
            if(b!=-1)p[b]=i;
        }
        while(m--){
            int a,b;
            cin>>a>>b;
            int x=find(a,L),y=find(b,R);
            for(int i=x-1,j=y-1;i>=0&&j>=0;j--,i--){
                if(L[i]==R[j])x--,y--;
                else break;
            }
            cout<<x+y<<endl;
        }
    }

    return 0;
}

• spfa

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1010,M=20010;
int h[N],e[M],ne[M],idx;
bool st[N];
int dist[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int n,m,t;
int spfa(int start,int end){
    memset (dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    queue<int>q;
    dist[start]=0;
    st[start]=true;
    q.push(start);
    while(q.size()){
        int u=q.front();
        if(u==end)return dist[u];
        q.pop();
        st[u]=false;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[u]+1){
                dist[j]=dist[u]+1;
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return dist[end];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>t;
    while(t--){
        memset(h,-1,sizeof h);
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            if(x!=-1)add(i,x),add(x,i);
            if(y!=-1)add(i,y),add(y,i);
        }
        while(m--){
            int a,b;
            cin>>a>>b;
            cout<<spfa(a,b)<<endl;
        }
    }
    
    
    return 0;
}