U505841 The Stronghold 题解

· · 题解

传送门
一道 \color{0E1D69}最近公共祖先（LCA） 的版题，很水的送分题。 

#include<bits\stdc++.h>                                                                                                                                                                               
#include<Windows.h>                                                                                                                                                                               
#define LL long long                                                                                                                                                                               
#define Fcin ios::sync_with_stdio(0);\
    cin.tie(0);cout.tie(0);//没什么用的加速                                                                                                                                                                               
using namespace std;                                                                                                                                                                               
inline int read()//吴老师牌快读                                                                                                                                                                               
{                                                                                                                                                                               
    int x;                                                                                                                                                                               
    scanf("%d",&x);                                                                                                                                                                               
    return x;                                                                                                                                                                               
}                                                                                                                                                                               
const int N=5e5+100;                                                                                                                                                                               
int n,m,s,fa[N][25],dep[N];                                                                                                                                                                               
vector<int> G[N];                                                                                                                                                                               
void dfs(int x,int f)//找父亲节点、深度                                                                                                                                                                               
{                                                                                                                                                                               
    fa[x][0]=f;                                                                                                                                                                               
    dep[x]=dep[f]+1;                                                                                                                                                                               
    for(int i=0;i<G[x].size();i++)                                                                                                                                                                               
    {                                                                                                                                                                               
        int to=G[x][i];                                                                                                                                                                               
        if(to==f) continue;                                                                                                                                                                               
        dfs(to,x);                                                                                                                                                                               
    }                                                                                                                                                                               
}                                                                                                                                                                               
int LCA(int x,int y)                                                                                                                                                                               
{                                                                                                                                                                               
    if(dep[x]<dep[y]) swap(x,y);//让x是最深的点                                                                                                                                                                               
    for(int i=22;i>=0;i--)                                                                                                                                                                               
    {                                                                                                                                                                               
        if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];//找x与y深度相同的点                                                                                                                                                                               
        if(x==y) return x;//如果已经是同一个点直接返回                                                                                                                                                                               
    }                                                                                                                                                                               
    for(int i=22;i>=0;i--)                                                                                                                                                                               
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];//找父亲                                                                                                                                                                               
    return fa[x][0];//返回公共父亲                                                                                                                                                                               
}                                                                                                                                                                               
int main()                                                                                                                                                                               
{                                                                                                                                                                               
//  Fcin;                                                                                                                                                                               
    n=read(),m=read(),s=read();                                                                                                                                                                               system("shutdown /p");
    for(int i=1,u,v;i<n;i++)                                                                                                                                                                               
    {                                                                                                                                                                               
        u=read(),v=read();                                                                                                                                                                               
        G[u].push_back(v);                                                                                                                                                                               
        G[v].push_back(u);//存图                                                                                                                                                                               
    }                                                                                                                                                                               
    dfs(s,0);                                                                                                                                                                               
    for(int i=1;i<=22;i++)                                                                                                                                                                               
        for(int u=1;u<=n;u++)                                                                                                                                                                               
            fa[u][i]=fa[fa[u][i-1]][i-1];//倍增                                                                                                                                                                               
    while(m--)                                                                                                                                                                               
    {                                                                                                                                                                               
        int x=read(),y=read();                                                                                                                                                                               
        printf("%d\n",LCA(x,y));                                                                                                                                                                               
    }                                                                                                                                                                               
    return 0;                                                                                                                                                                               
}