LCA问题

一颗有根树，每个点都有若干祖先（自己也是自己的祖先）。两个点最近的一个公共祖先称为它们的公共祖先。

方法：倍增

先预处理:

f[i][j]表示i向上走 $2^j $步的祖先结点，递推公式f[i][j]=f[f[i][j-1]][j-1] (n log n)

depth[i]表示i的深度，规定根节点的深度是1，i的深度是到根节点的距离+1。

规定：f[i][j]跳过了，f[i][j]=0 depth[i]=0

求x和y的LCA，分两步来做。先将更深的点跳到浅点的那一层(log n)。然后假设同时往上跳k层，从大到小找k的二进制表示，跳到LCA为止（ log n）。

方法：tarjan (离线)

在线做法：边读边做
离线做法：先读完，再全部处理，最后全部输出。

Tarjon本质就是对向上标记法的一个优化，任取一个节点当成根节点进行dfs优先遍历，把所有节点分成三部分
1）已经遍历并且回溯的标记成2
2）正在遍历的没有回溯的标记成1
3）未遍历的标记成0

注意：顺序一定不能乱。
1）当这个点遍历子节点后的时候把子节点的祖宗更新成当前点
2）只有当前点回溯的时候才可以用这个点来计算所有之前为2的点，因为如果当前点为a,而b是a这条路径的上的点，并且b在a的下面，那么因为b先回溯，所以要等b回溯了之后才能正确的判断a。

祖孙询问

题意：比较裸的LCA，用倍增做

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 40010,M=80010,INF = 0x3f3f3f3f;

int n,m;
vector<int> mp[N];
int depth[N],fa[N][16];
int q[N];

void bfs(int root){
    memset(depth,0x3f,sizeof depth);
    depth[0] = 0,depth[root] =1;
    int hh=0,tt=0;
    q[0] = root;
    while(hh<=tt){
        int t = q[hh++];
        for(auto nw:mp[t]){
            if(depth[nw]>depth[t]+1){
                depth[nw]=depth[t]+1;
                q[++tt] = nw;
                fa[nw][0] = t;
                for(int i=1;i<=15;i++)
                    fa[nw][i] = fa[fa[nw][i-1]][i-1];
            }
        }
    }
}

int lca(int a,int b){
    if(depth[a] < depth[b]) swap(a,b);
    for (int k = 15; k >= 0; k -- ){
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    }
    if(a == b) return a;

    for(int k=15;k>=0;k--){
        if(fa[a][k] != fa[b][k]){
            a = fa[a][k];
            b = fa[b][k];
        }
    }

    return fa[a][0];
}

int main(){
    scanf("%d",&n);
    int root =0;
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(b == -1) root = a;
        else{
            mp[a].push_back(b);
            mp[b].push_back(a);
        }
    }
    bfs(root);
    scanf("%d",&m);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        int p = lca(a,b);
        if(p==a) puts("1");
        else if(p==b) puts("2");
        else puts("0");
    }
    return 0;
}

技巧总结：bfs的时候就把 f 和 depth 建好。

距离

题意：给出 n 个点的一棵树，多次询问两点之间的最短距离。

思考：LCA，用tarjan

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 30010,M=30010,INF = 0x3f3f3f3f;

int n,m;
vector<PII> mp[N];
int dist[M];
int p[N];
int res[N];
int st[N];

vector<PII> query[N];

int find(int x){
    if(p[x] != x) p[x] =find(p[x]);
    return p[x];
}

void dfs(int u,int fa){
    for(auto nw:mp[u]){
        int j=nw.first;
        if(j==fa) continue;
        dist[j] = dist[u]+nw.second;
        dfs(j,u);
    }
}

void tarjan(int u){
    st[u] = 1;
    for(auto nw:mp[u]){
        int j=nw.first;
        if(!st[j]){
            tarjan(j);
            p[j]=u;
        }
    }
    for(auto item:query[u]){
        int y=item.first,id=item.second;
        if(st[y] == 2){
            int anc=find(y);
            res[id] = dist[u] + dist[y] - dist[anc]*2;
        }
    }
    st[u] =2;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        mp[a].push_back({b,c});
        mp[b].push_back({a,c});
    }

    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a!=b){
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }
    for(int i=0;i<=n;i++) p[i]=i;

    dfs(1,-1);
    tarjan(1);
    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}