首页 > itarticle > [luogu

[luogu

admin 11月 14, 2020 0

链接

(text{Luogu - P3379})

题意

给定一颗树，还有一定数量的询问，对于每个询问，输出它的(text{LCA})。

分析

裸的(text{LCA})，这里先给出(text{Tarjan})的写法，实际上这里用(text{Tarjan})是不太好的，一开始没加入读入优化，有些数据过大直接(text{TLE})了，加了之后才(text{AC})，倍增和(text{ST})表之后再补。

关于(text{Tarjan})

(text{Tarjan})的实现是这样的:首先沿着根节点(dfs)访问与它相邻的节点，并标记这个点，这样当访问完某个子树的某个节点之后，用数组标记它的父节点，当还没有向上回溯的时候，开始遍历查询(读入的时候把询问存起来，正所谓离线)，查询与当前子树的根节点即当前节点(假设当前节点为(u))有关的询问((u,v))，如果与当前节点(即(u))查询有关的查询的另一个节点(即(v))已经在之前(dfs)过程中被访问过了，那么说明这个查询的(lca)就是节点(v)所在子树的根节点，因为你是(dfs)到(v)，然后(dfs)到(u)的，在你从(v)到(u)的这个过程中是肯定经过(lca)的；

注意，虽然说这里是一个子树，但他并没有形成集合上的树(就是假如用(f[i])存这颗树，但这个形成树的过程就是(dfs)到叶子节点，然后开始向上回溯的时候开始建立联系开始的，你一开始从根节点向下遍历的时候，实际上是不存在的，仅仅是一个图而不是树，建议模拟一下，画个图，把(f[i])的具体变化看一下)，只是存在边的联系，在访问完整个图后，才有了树；

建立画个图照着代码模拟一下；

代码


#include<string>
#include<queue>
#include<set>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const double inf=0x7f7f7f7f;
const int maxn=5e5+50;
const int N=5e3+50;
typedef long long ll;
typedef struct{
    int u,v,next,lca;
}Edge;

Edge e[2*maxn],query[2*maxn];

int cnt,head[maxn],head1[maxn],cnt1;

void (int u,int v){
    e[cnt].u=u;
    e[cnt].v=v;
    /*e[cnt].w=w;
    e[cnt].f=f;*/
    e[cnt].next=head[u];
    head[u]=cnt++;
    e[cnt].u=v;
    e[cnt].v=u;
/*	e[cnt].w=0;
    e[cnt].f=-f;*/
    e[cnt].next=head[v];
    head[v]=cnt++;
}
//用来存query即存查询
void addp(int u,int v){
    query[cnt1].u=u;
    query[cnt1].v=v;
    /*e[cnt].w=w;
    e[cnt].f=f;*/
    query[cnt1].next=head1[u];
    head1[u]=cnt1++;
    query[cnt1].u=v;
    query[cnt1].v=u;
/*  e[cnt].w=0;
    e[cnt].f=-f;*/
    query[cnt1].next=head1[v];
    head1[v]=cnt1++;
}
int read()
{
    int x = 0;
    int f = 1;
    char c = getchar();
    while (c<'0' || c>'9')
    {    
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x*f;
}

int n,m,s,f[maxn],vis[maxn];

int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}


void tarjan(int x){
    vis[x]=1;
    f[x]=x;
    for(int i=head[x];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(!vis[v]){
            tarjan(v);
            f[v]=x;
        }
    }
    for(int i=head1[x];i!=-1;i=query[i].next){
        int v=query[i].v;
        if(vis[v]){
            query[i].lca=find(v);
            query[i^1].lca=f[v];
        }
    }
}
int main() {
   // std::ios::sync_with_stdio(false);
    n=read(),m=read(),s=read();
    int u,v;
    memset(head,-1,sizeof(head));
    memset(head1,-1,sizeof(head1));
    for(int i=0;i<n-1;i++){
        u=read(),v=read();
        add(u,v);
    }
    for(int i=0;i<m;i++){
        u=read(),v=read();
        addp(u,v);
    } 
    tarjan(s);
    for(int i=0;i<cnt1;i+=2){
        cout<<query[i].lca<<endl;
    }
    return 0;
}