LCA offline algorithm

LCA problem: given a rooted tree T, for any two nodes u,v to find LCA (T, u,v), that is, from the root most
The distant node x makes x the ancestor of both u and v.

Think of LCA questions as inquiry: give a series of inquiries, and the program should respond to each inquiry as soon as possible.
There are two solutions to this kind of problem: one is to preprocess for a long time, but every time when the information is sufficient
It takes less time to answer questions. Such an algorithm is called an online algorithm. Another kind of algorithm is to read in all the queries first, and then complete all the queries together. Such an algorithm is called offline algorithm. The problems they solve are interrogative, but the methods and characteristics are different, and the scope of application is also different (if the query is given with interval, often only online algorithm can be used).

Online algorithm is more complex than offline algorithm, so only the following offline algorithm is learned first, most of the online description is not very clear

This is a super detailed blog
http://www.cnblogs.com/JVxie/p/4854719.html

Tarjan algorithm template

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int N = 40010;
const int M = 410;

int head[N];            //Header of tree edge adjacency table
int __head[N];          //Save the header of the adjacency table of the query
struct edge{            //Save edge
    int u,v,w,next;
}e[2*N];
struct ask{            //Preservation inquiry
    int u,v,lca,next;
}ea[M];
int dir[N];              //Distance from savepoint to tree root
int fa[N];               //Check the set and save the representative elements of the set
int ance[N];             //Save the combination of sets, notice that the object is a set rather than an element
bool vis[N];             //Array of tags when traversing

inline void add_edge(int u,int v,int w,int &k) //Save edge
{
    e[k].u = u; e[k].v = v; e[k].w = w;
    e[k].next = head[u]; head[u] = k++;
    u = u^v; v = u^v; u = u^v;
    e[k].u = u; e[k].v = v; e[k].w = w;
    e[k].next = head[u]; head[u] = k++;
}

inline void add_ask(int u ,int v ,int &k) //Preservation inquiry
{
    ea[k].u = u; ea[k].v = v; ea[k].lca = -1;
    ea[k].next = __head[u]; __head[u] = k++;
    u = u^v; v = u^v; u = u^v;   ///It looks profound.. In fact, it is swap(u,v);
    ea[k].u = u; ea[k].v = v; ea[k].lca = -1;
    ea[k].next = __head[u]; __head[u] = k++;
}

int Find(int x)
{
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
void Union(int u ,int v)
{
    fa[v] = fa[u];  //It can be written as fa[Find(v)] = fa[u];
}

void Tarjan(int u)
{
    vis[u] = true;
    ance[u] = fa[u] = u; //It can be written as ance[Find(u)] = fa[u] = u;
    for(int k=head[u]; k!=-1; k=e[k].next)
        if( !vis[e[k].v] )
        {
            int v = e[k].v , w = e[k].w;
            dir[v] = dir[u] + w;
            Tarjan(v);
            Union(u,v);
            ance[Find(u)] = u;  
        }
    for(int k=__head[u]; k!=-1; k=ea[k].next)
        if( vis[ea[k].v] )
        {
            int v = ea[k].v;
            ea[k].lca = ea[k^1].lca = ance[Find(v)];
        }
}

int main()
{
    int tcase;
    scanf("%d",&tcase);
    while(tcase--){
    int n,q;
    scanf("%d%d",&n,&q);
    memset(head,-1,sizeof(head));
    memset(__head,-1,sizeof(__head));
    int tot = 0;
    for(int i=1; i<n; i++)  //Build up trees
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w,tot);
    }
    tot = 0;
    for(int i=0; i<q; i++) //Open save query
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add_ask(u,v,tot);
    }
    memset(vis,0,sizeof(vis));
    dir[1] = 0;
    Tarjan(1);
    for(int i=0; i<q; i++)
    {
        int s = i * 2 , u = ea[s].u , v = ea[s].v , lca = ea[s].lca;
        printf("%d\n",dir[u]+dir[v]-2*dir[lca]);
    }
    }

    return 0;
}

Tags: less

Posted on Thu, 28 Nov 2019 09:52:51 -0800 by dniry