Luogu P3379 [template] recent common ancestor (LCA) (online multiplication + offline Tarjan)

Title Description

For example, given a tree with multiple forks, the nearest common ancestor of two specified points is requested.

Input format:

The first row contains three positive integers N, M and S, which respectively represent the number of nodes in the tree, the number of queries and the serial number of the root node of the tree.

Next, each row of N-1 contains two positive integers x and y, indicating that there is a direct connection between X and Y nodes (data guarantee can form a tree).

Next, each row of row M contains two positive integers a and b, indicating the nearest common ancestor of query a and b nodes.

Output format:

The output contains M lines, and each line contains a positive integer, which is the result of each query in turn.

Input example ා 1:

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

Output example:

4
4
1
4
4

thinking

As its name implies, it is the template of lca. I'll save my lca template~

Offline Tarjan

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;
int pre[N],first[N],first2[N],tot,tot2;
bool vis[N];//Mark whether to ask
int n;
struct edge
{
    int v,next;
} e[2*N];
struct Query
{
    int v,w,next;
} query[2*N];

void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}

void add_query(int u,int v)
{
    query[tot2].v=v;
    query[tot2].w=-1;
    query[tot2].next=first2[u];
    first2[u]=tot2++;
}

int find(int x)
{
    return x==pre[x]?x:pre[x]=find(pre[x]);
}
void mix(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        pre[fy]=fx;
}

int lca(int u,int fa)
{
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa) continue;
        lca(v,u);
        pre[v]=u;
    }
    vis[u]=1;
    for(int i=first2[u]; ~i; i=query[i].next)
    {
        int v=query[i].v;
        if(vis[v])
            query[i].w=find(v);
    }
}

void init()
{
    mem(first,-1);
    mem(first2,-1);
    mem(vis,0);
    tot=0;
    tot2=0;
    for(int i=1; i<=n; i++)
        pre[i]=i;
}

int main()
{
    int m,s,u,v;
    scanf("%d%d%d",&n,&m,&s);
    init();
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        add_query(u,v);
        add_query(v,u);
    }
    lca(s,pre[s]);
    for(int i=0; i<tot2; i++)
        if(query[i].w!=-1)
            printf("%d\n",query[i].w);
    return 0;
}

Online multiplication

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;

int n,m,s;
int tot;
int first[N],d[N],p[N][21];

struct edge
{
    int v,next;
} e[2*N];

void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}

void dfs(int u,int fa)
{
    d[u]=d[fa]+1;
    p[u][0]=fa;
    for(int i=1; (1<<i)<=d[u]; i++)
        p[u][i]=p[p[u][i-1]][i-1];
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa)
            dfs(v,u);
    }
}

int lca(int a,int b)
{
    if(d[a]>d[b]) swap(a,b);//Make sure a is above point b
    for(int i=20; i>=0; i--)
        if(d[a]<=d[b]-(1<<i))
            b=p[b][i];  //Move b to the same depth as a
    if(a==b) return a;
    for(int i=20; i>=0; i--)
    {
        if(p[a][i]==p[b][i])
            continue;
        else
            a=p[a][i],b=p[b][i];//Jump up together
    }
    return p[a][0];
}


void init()
{
    tot=0;
    mem(first,-1);
    mem(d,0);
    mem(p,0);
}
int main()
{
    init();
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&a,&b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs(s,0);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}

Posted on Thu, 30 Apr 2020 09:31:41 -0700 by Chiaki