pog loves szh III

发表于

倍增法求LCA

暴力

首先把u,v中深度最大的结点提到和另一结点相同的深度，然后暴力一起向上，知道u=v为止。

祖先

对于一颗树的一个结点u ，她的爸爸的爸爸是她的祖先，她的爸爸的祖先也是她的祖先…..以此类推，直到根结点，根结点也是她的祖先。

公共祖先

对于一棵树的两个结点u, v,u,v的共同的祖先称作她们的公共祖先。

LCA

指u,v最近公共祖先，记为LCA(u, z)。最近公共祖先也就是u,v的公共祖先中最深的。

暴力相当于每次只跳2^0^步，而倍增通过从大到小枚举2的次幂，在枚举到每个i时会以下跳2^i^次，在倍增中只跳一次，暴力却需要2的i次方倍。

为什么i只需要20呢，因为y=2^x^的增长速度是指数级别。

2^17^=131072基本满足题目数据范围。

image-20210723172922189

pog loves szh III

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std ;
typedef long long LL ;
const int N = 400030 ;
const int DEG = 30 ;
int n;

struct Edge{
    int to,next;
}edge[N<<1];

int head[N],tot;

void add(int u,int v){//链式前向星
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}



int fa[N][DEG] , deg[N];

void dfs(int u) {
    for(int i=head[u]; i!=-1; i=edge[i].next) {
        int to=edge[i].to;
        if(to==fa[u][0])
            continue;
        deg[to]=deg[u]+1;//深度信息储存
        fa[to][0]=u;
        dfs(to);
    }
}
void F()//i的2^j祖先就是i的（2^(j-1))祖先的2^(j-1)祖先
{
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i<=n; i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
}

int LCA(int u,int v)
{
    if(deg[u] > deg[v])swap(u,v);
    int u1 = deg[u], v1 = deg[v];
    int u2 = u, v2 = v;
       int det = v1-u1;
   for( int i = 0 ;(1<<i)<=det;i++)
        if((1<<i)&det)
            v2 = fa[v2][i];
    if(u2 == v2)return u2;
    for(int i = DEG-1; i >= 0; i--)  //从最大祖先开始，判断a,b祖先，是否相同
    {
        if(fa[u2][i] == fa[v2][i])
            continue;
        u2 = fa[u2][i];            //如不相同，a b同时向上移动2^j
        v2 = fa[v2][i];
    }
    return fa[u2][0];              
}
void init(){
    tot = 0;
    memset(head,-1,sizeof(head));
}
int main()
{
    ios::sync_with_stdio(false);
    while(scanf("%d",&n)!=EOF){
        init();
        for( int i = 1 ; i < n ; ++i ) {
            int u , v ;
            cin>>u>>v;
            add( u , v ) ;
            add( v , u ) ;
        }
        dfs(1);
        F();
        int q ;
        cin>>q;
        while( q-- ) {
            int x , y ;
            scanf("%d%d",&x,&y);
           // cin>>x>>y;
            cout<<LCA(x,y)<<endl;
        }
    }
    return 0;
}