P3379 LCAtarjan

· · 题解

看到题解基本上都是倍增做法，找了半天tarjan的代码都没找到QAQ，我就提供一个tarjan代码好了

tarjan我个人理解就是：从叶到根依次选取节点（用dfs+回溯），然后把选取的节点查询子树，那么子树中的所有节点的公共祖先都是这个节点，那么查询的第一个的子树节点有包括(u,v)便是(u,v)的最近公共祖先。

tarjan具体做法请看这个博客

我认为tarjan做法真的很巧妙，每次选取节点时利用并查集把所有的点的公共祖先转移了。

我这个代码是用vector储存边，用前向星（结构体Edge）储存的询问问题和问题答案，然后每个问题储存两次，那么肯定会有一个答案为0。当然也可以直接再开一个数组来储存答案。

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pc(a) putchar(a)
#define rg register
const ll maxn=500001;
const ll maxm=500001;
void gc(char &a)
{
    a=getchar();
    while(a==' '||a=='\n') a=getchar();
}
ll read(){
    char c;ll x=0;bool flag=0;gc(c);
    while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),c=getchar();}
    return flag?-x:x;
}
void pr(ll x){
    if(x<0){x=-x;pc('-');}
    if(x>9) pr(x/10);
    pc(x%10+48);
}
//----------快读-------------
struct Edge
{
    ll v,nx,dis;//dis为答案
    Edge(ll v,ll nx):v(v),nx(nx){this->dis=0;}
    Edge(){}
}edge[maxm<<1];
ll head[maxn],en;
void edgepush(ll u,ll v)
{
    edge[++en]=Edge(v,head[u]);
    head[u]=en;
}
ll fa[maxn],n,m,e;
vector<ll> tree[maxn];
bool flag[maxn];
int find(ll u){
    return u==fa[u]?u:fa[u]=find(fa[u]);
}//超短并查集
void dfs(ll u,ll f)
{
    fa[u]=u;
    for(int v,i=0;i<tree[u].size();i++)
    {
        v=tree[u][i];
        if(f==v) continue;//因为是无向图，防止死循环
        dfs(v,u);
        fa[find(v)]=u;
    }//遍历子树
    flag[u]=1;
    for(int v,i=head[u];i;i=edge[i].nx)
    {
        v=edge[i].v;
        if(flag[v]&&!edge[i].dis) 
        edge[i].dis=find(v);
    }//查询答案
}
int main()
{
    n=read(),m=read(),e=read();
    for(int u,v,i=1;i<n;i++)
    {
        u=read(),v=read();
        tree[u].push_back(v);
        tree[v].push_back(u);
    }//建树
    for(int u,v,i=1;i<=m;i++)
    {
        u=read(),v=read();
        edgepush(u,v);
        edgepush(v,u);
    }//建问题
    dfs(e,-1);//遍历
    for(int i=1;i<=(m*2);i++)
    if(edge[i].dis)
    {
        pr(edge[i].dis);
        pc('\n');//换行
    }
}