P3379 【模板】最近公共祖先（LCA）

PrincessYR✨～ · 2019-12-11 19:10:37 · 个人记录

这道题值得一刷

because of：WA

题解里的巨佬都用Tarjan（窝太难了）

实际上是他们太巨了

本人马蜂码风独特，请见谅

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void out(int a){
   if(a<0) putchar('-'),a/=-1;
   if(a>9) out(a/10);
   putchar(a%10+'0');
}
int a,b,c,d,e,shen[500005],par[20][500005],q1,q2, MAX_LOG_N;
vector<int> q[500005];
void dfs(int v,int p,int d)
{
    par[0][v]=p;
    shen[v]=d;
    for(int i=0;i<q[v].size();i++)
    {
        if(q[v][i]!=p) dfs(q[v][i],v,d+1);
    }
}
void cl()
{
    for(int k=0;k+1<MAX_LOG_N;k++)
    {
        for(int v=1;v<=a;v++)
        {
            if(par[k][v]<0)
            par[k+1][v]=-1;
            else 
            par[k+1][v]=par[k][par[k][v]];
        }
    }
}
int lca(int u,int v)
{
    if(shen[u]>shen[v])
    swap(u,v);
    for(int k=0;k<MAX_LOG_N;k++)
    {
        if(shen[v]-shen[u]>>k&1)
        {
            v=par[k][v];
        }
    }
    if(u==v)
    return u;
    for(int k=MAX_LOG_N-1;k>=0;k--)
    {
        if(par[k][v]!=par[k][u])
        {
            u=par[k][u];
            v=par[k][v];
        }
    }
    return par[0][u];
}
int main()
{
    a=read();b=read();c=read();
    MAX_LOG_N=log(a)/log(2);
    for(int i=1;i<a;i++)
    {
        d=read();e=read();
        q[d].push_back(e);
        q[e].push_back(d);
    }
    dfs(c,-1,0);
    cl();
    for(int i=1;i<=b;i++)
    {
        q1=read();q2=read();
        out(lca(q1,q2));
        putchar('\n');
    }
    return 0;
}

事实证明read（），write（）（他不香吗）真香，给谁谁不香

童鞋的教训

都看到这里了，不点赞吗！