HDU5266 LCA 树链剖分LCA 线段树

HDU5266 LCA

Description

给一棵 n 个点的树，Q 个询问 [L,R] : 求点 L , 点 L+1 , 点 L+2 …… 点 R 的 LCA.

Input

多组数据.

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

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

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

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

Output

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

Sample Input

Sample Output

solution

这题其实就是求[l,r]区间内的公共lca。

既,

\[ans(l,r)=LCA(a_l,a_{l+1},a_{l+2}\cdots a_r)
\]

这里有一个显而易见的结论

\[LCA(x,y,z)=LCA\bigl(LCA(x,y),z\bigr)=LCA\bigl(LCA(z,y),x\bigr)=LCA\bigl(LCA(z,x),y\bigr)
\]

所以我们在这里考虑建一棵线段树，每次pushup向上更新lca，我们可以用树剖来求lca，这样我们就可以求出区间lca了

这是代码

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=300001,inf=0x7fffffff;

int n,m,tot,root,nxt[maxn<<1],to[maxn<<1],head[maxn],lca[maxn<<2],dep[maxn],siz[maxn],top[maxn],fa[maxn],son[maxn];

bool check[maxn];

void addedge(int x,int y){

    nxt[++tot]=head[x];

    head[x]=tot;

    to[tot]=y;

}

void dfs1(int u,int f) {

    dep[u]=dep[fa[u]=f]+(siz[u]=1);

    for(int i=head[u];i;i=nxt[i]) {

        int v=to[i];

        if(v==f)continue;

        dfs1(v,u);

        siz[u]+=siz[v];

        if(siz[v]>siz[son[u]])son[u]=v;

    }

}

void dfs2(int u,int topf){

    top[u]=topf;

    if(!son[u])return;

    dfs2(son[u],topf);

    for(int i=head[u];i;i=nxt[i]){

        int v=to[i];

        if(v==fa[u] or v==son[u])continue;

        dfs2(v,v);

    }

}

int Lca(int x,int y) {

    register int u=x,v=y;

    while(top[u]!=top[v]) {

        if(dep[top[u]]<dep[top[v]])swap(u,v);

        u=fa[top[u]];

    }

    return dep[u]<=dep[v]?u:v;

}

void pushup(int o){

    lca[o]=Lca(lca[o<<1],lca[o<<1|1]);

}

void build(int o,int l,int r){

    if(l==r){

        lca[o]=l;

        return;

    }

    int mid=l+r>>1;

    build(o<<1,l,mid);

    build(o<<1|1,mid+1,r);

    pushup(o);

}

int query(int o,int l,int r,int x,int y){

    if(x<=l and r<=y){

        return lca[o];

    }

    int mid=l+r>>1,ans1=-1,ans2=-1;

    if(x<=mid)ans1=query(o<<1,l,mid,x,y);

    if(mid+1<=y)ans2=query(o<<1|1,mid+1,r,x,y);

    if(ans1!=-1 and ans2!=-1)return Lca(ans1,ans2);

    if(ans1!=-1)return ans1;

    if(ans2!=-1)return ans2;

}

int main(){

    while(~scanf("%d",&n)){

        tot=0;

        memset(fa,0,sizeof(fa));

        memset(son,0,sizeof(son));

        memset(head,0,sizeof(head));

        for(int i=1;i<n;i++){

            int u,v;

            scanf("%d%d",&u,&v);

            addedge(u,v),addedge(v,u);

        }

        dfs1(1,0);

        dfs2(1,1);

        build(1,1,n);

        scanf("%d",&m);

        while(m--){

            int l,r;

            scanf("%d%d",&l,&r);

            printf("%d\n",query(1,1,n,l,r));

        }

    }

    return 0;

}

巴特西