[Luogu - P3379] 最近公共祖先

发表于 | 更新于 | 分类于 ， ，
本文字数： 16k

链接

\(\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]\)的具体变化看一下)，只是存在边的联系，在访问完整个图后，才有了树；

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<iostream>
#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;
//e用来存边，query存查询
Edge e[2*maxn],query[2*maxn];

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

void add(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;
}