pog loves szh III HDU - 5266(LCA最近公共祖先)

Pog and Szh are playing games. Firstly Pog draw a tree on the paper. Here we define 1 as the root of the tree.Then Szh choose some nodes from the tree. He wants Pog helps to find the least common ancestor (LCA) of these node.The question is too difficult for Pog.So he decided to simplify the problems.The nodes picked are consecutive numbers from lili to riri ([li,ri])([li,ri]).

Hint : You should be careful about stack overflow !

Input

Several groups of data (no more than 3 groups,n≥10000n≥10000 or Q≥10000Q≥10000).

The following line contains ans integers,n(2≤n≤300000)n(2≤n≤300000).

AT The following n−1n−1 line, two integers are bibi and cici at every line, it shows an edge connecting bibi and cici.

The following line contains ans integers,Q(Q≤300000)Q(Q≤300000).

AT The following QQ line contains two integers li and ri(1≤li≤ri≤n1≤li≤ri≤n).

Output

For each case,output QQ integers means the LCA of [li,ri][li,ri].

Sample Input

5

1 2

1 3

3 4

4 5

5

1 2

2 3

3 4

3 5

1 5

Sample Output

1

1

3

3

1

Hint

Be careful about stack overflow.

求LCA最近公共祖先有3種方法：

  1：線上算法  dfs序+線段樹（或dfs序+rmq，rmq要更快，本人rmq較弱是以就用線段數将就一下）

  2：離線算法  tarjan 

  3：線上算法  樹鍊剖分（這個是非正常求法，這篇部落格就不講了，想了解的：傳送門）  

1. dfs序+線段樹

  dfs深搜得到dfs序，當詢問節點l和r的LCA時，隻需用線段樹在dfs序中找到深度最小的節點，此節點就是LCA

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

const int inf=0x3f3f3f3f;
vector<int>vec[300005];
int dfsx[600005],dfsx2[600005],dfsn,first[300005],tree[2400005],tree2[2400005],dist[300005],vis[300005],n;///tree2[]為查詢樹

void dfs(int x)///求dfs序
{
    vis[x]=1;
    dfsx[++dfsn]=x;
    dfsx2[dfsn]=dist[x];
    first[x]=dfsn;
    for(int i=0;i<vec[x].size();i++){
        int v=vec[x][i];
        if(vis[v]==0){
            dist[v]=dist[x]+1;
            dfs(v);
            dfsx[++dfsn]=x;
            dfsx2[dfsn]=dist[x];
        }
    }
}

void up(int root)///線段樹 合并
{
    int ll=tree[root<<1],rr=tree[root<<1|1];
    if(dfsx2[ll]>dfsx2[rr]){tree[root]=rr;return;}
    tree[root]=ll;
}

void maketree(int l,int r,int root)///線段樹 建樹
{
    if(l==r){tree[root]=l;return;}
    int mid=(l+r)>>1;
    maketree(l,mid,root<<1);
    maketree(mid+1,r,root<<1|1);
    up(root);
}

void up2(int root)///線段樹 合并
{
    int ll=tree2[root<<1],rr=tree2[root<<1|1];
    if(dfsx2[ll]>dfsx2[rr]){tree2[root]=rr;return;}
    tree2[root]=ll;
}

void zhao(int l,int r,int root,int ll,int rr)///線段樹 查找
{
    if(r<ll||l>rr){tree2[root]=0;return;}
    if(l>=ll&&r<=rr){
        tree2[root]=tree[root];
        return;
    }
    int mid=(l+r)>>1;
    zhao(l,mid,root<<1,ll,rr);
    zhao(mid+1,r,root<<1|1,ll,rr);
    up2(root);

}

void init()
{
    for(int i=1;i<=n;i++){
        vis[i]=0;
        vec[i].clear();
    }
}

int main()
{
    dfsx2[0]=inf;
    while(scanf("%d",&n)!=EOF){
        init();
        int a,b;
        for(int i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
        dfsn=0;
        dist[1]=1;
        dfs(1);
        maketree(1,dfsn,1);
        int m;
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&a,&b);
            int l=first[a],r=first[b];
            if(l>r)swap(l,r);
            zhao(1,dfsn,1,l,r);
            printf("%d\n",dfsx[tree2[1]]);
        }
    }
    return 0;
}
           

2.離線算法 tarjan

  先将詢問儲存，然後dfs周遊,從子節點傳回時要用并查集合并，當周遊到一個節點u時，檢視所有的“詢問對”u<->v，當v已經被dfs通路并标記時，此“詢問對”u<->v的LCA就為fa[v]。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=40010;

struct note
{
    int u,v,w,lca,next;
}edge[maxn*2],edge1[805];

int head[maxn],ip,head1[maxn],ip1;
int m,n;
int father[maxn],vis[maxn],ance[maxn],dir[maxn];

void init()
{
    memset(vis,0,sizeof(vis));
    memset(dir,0,sizeof(dir));
    memset(head,-1,sizeof(head));
    memset(head1,-1,sizeof(head1));
    ip=ip1=0;
}

void addedge(int u,int v,int w)
{
    edge[ip].v=v,edge[ip].w=w,edge[ip].next=head[u],head[u]=ip++;
}

void addedge1(int u,int v)
{
    edge1[ip1].u=u,edge1[ip1].v=v,edge1[ip1].lca=-1,edge1[ip1].next=head1[u],head1[u]=ip1++;
}

int  Find(int x)///路徑壓縮
{
    if(father[x]==x)
        return x;
    return father[x]=Find(father[x]);
}

void Union(int x,int y)///x,y合并
{
    x=Find(x);
    y=Find(y);
    if(x!=y)
        father[y]=x;
}

void tarjan(int u)
{
    vis[u]=1;
    ance[u]=father[u]=u;
    for(int i=head[u];i!=-1;i=edge[i].next)///往下深搜
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(!vis[v])
        {
           dir[v]=dir[u]+w;
           tarjan(v);
           Union(u,v);
        }
    }
    for(int i=head1[u];i!=-1;i=edge1[i].next)///
    {
        int v=edge1[i].v;
        if(vis[v])///v已經被通路并标記，可以得出此詢問的結果
        {
            edge1[i].lca=edge1[i^1].lca=ance[Find(v)];///此詢問對u,v和詢問對v,u都會得出答案
        }
    }
}
int main()
{
   int T;
   scanf("%d",&T);
   while(T--)
   {
       init();
       scanf("%d%d",&n,&m);
       for(int i=1;i<n;i++)
       {
           int u,v,w;
           scanf("%d%d%d",&u,&v,&w);
           addedge(u,v,w);
           addedge(v,u,w);
       }
       for(int i=0;i<m;i++)
       {
           int u,v;
           scanf("%d%d",&u,&v);
           addedge1(u,v);
           addedge1(v,u);
       }
       dir[1]=0;
       tarjan(1);
       for(int i=0;i<m;i++)
       {
           int s=i*2,u=edge1[s].u,v=edge1[s].v,lca=edge1[s].lca;
           printf("%d\n",dir[u]+dir[v]-2*dir[lca]);
       }
   }
   return 0;
}