lca倍增模板

Posted on | In ,

lca即最近公共祖先，倍增法可以在O(n)的预处理后以每次logn的代价进行查询操作。

思路：预处理出fa[n][i]数组，表示第n号点的第（1<<i）个父亲，之后在寻找u、v的lca时，可以对二进制上的每一位进行向上跳跃。

例题：cf1304E

给出一棵树，有q个询问，格式（x，y，a，b，k）。意为对x，y点连边，求问此时从a到b有无一条长为k的路径，边可以重复走。

分析：边可以重复走说明如果一条路径长度小于k，且与k奇偶性相同，那么就可以重复走某些边来满足要求。添加bian（x，y）后，我们一共有三条可行的基础路径（a，b）、（a，x）+1+（y，b）、（a，y）+1+（x，b）。依次检查即可。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+1;

struct edge{
    int to,next;
}es[maxn*2];
int head[maxn];
int cnt;
void add(int u,int v){
    es[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}

int fa[maxn][31],dep[maxn];
void dfs(int o,int from){
    fa[o][0]=from;
    dep[o]=dep[fa[o][0]]+1;
    for(int i=1;i<31;i++){      //处理出o点的父亲链
        fa[o][i]=fa[fa[o][i-1]][i-1];
    }
    for(int i=head[o];i;i=es[i].next){
        int v=es[i].to;
        if(v==from) continue;
        dfs(v,o);
    }
}

int lca(int u,int v){
    if(dep[u]>dep[v])
        swap(u,v);
    int cha=dep[v]-dep[u];
    for(int i=0;(1<<i)<=cha;i++){   //拉平深度的差距
        if(cha&(1<<i)){
            v=fa[v][i];
        }
    }
    if(u==v) return u;
    for(int i=30;i>=0;--i){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[v][0];    //返回lca
}
int n,q;
int main(){
    cin>>n;
    int u,v;
    for(int i=0;i<n-1;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    cin>>q;
    int x,y,a,b,k;
    while(q--){
        cin>>x>>y>>a>>b>>k;
        bool f=false;
        int len=dep[a]+dep[b]-2*dep[lca(a,b)];
        if(len<=k&&(!((k-len)&1)))
            f=true;
        len=dep[a]+dep[x]-2*dep[lca(a,x)]+dep[b]+dep[y]-2*dep[lca(b,y)]+1;
        if(len<=k&&(!((k-len)&1)))
            f=true;
        len=dep[a]+dep[y]-2*dep[lca(a,y)]+dep[b]+dep[x]-2*dep[lca(b,x)]+1;
        if(len<=k&&(!((k-len)&1)))
            f= true;
        printf(f?"YES\n":"NO\n");
    }
    return 0;
}