欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

lca(树上倍增/st表)模板

程序员文章站 2024-01-14 16:31:22
...

树上倍增

struct LCA {
    int t, f[N][20], d[N];

    void dfs(int x) {
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if (d[y])continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for (int j = 1; j <= t; j++)
                f[y][j] = f[f[y][j - 1]][j - 1];
            dfs(y);
        }
    }

    inline int lca(int x, int y) {
        if (d[x] > d[y])swap(x, y);
        for (int i = t; i >= 0; i--)
            if (d[f[y][i]] >= d[x])
                y = f[y][i];
        if (x == y)
            return x;
        for (int i = t; i >= 0; i--)
            if (f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
        return f[x][0];
    }

    ll dis(int x, int y) {
        return d[x] + d[y] - 2 * d[lca(x, y)];
    }
};

//d[1]=1;
//t = (int) log2(n) + 1;
//dfs(1);

st

#include<bits/stdc++.h>

#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scahf("%c",&a);
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<long,long>
#define pil pair<int,long>
#define pli pair<long,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}
struct LCA {
    int vr[N * 4], depth[N * 4], first[N], tot;
    bool vis[N];
    int dp[N * 4][20];

    void dfs(int u, int dep) {
        vis[u] = true, vr[++tot] = u;
        first[u] = tot, depth[tot] = dep;
        reps(u) {
            int y = ver[i];
            if (!vis[y])
                dfs(y, dep + 1), vr[++tot] = u, depth[tot] = dep;
        }
    }

    void ST(int x) {
        repi(i, 1, x) dp[i][0] = i;
        for (int j = 1; (1 << j) <= x; j++) {
            for (int i = 1; i + (1 << j) - 1 <= x; i++) {
                int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1];
                dp[i][j] = depth[a] < depth[b] ? a : b;
            }
        }
    }

    int RMQ(int l, int r) {
        int k = log2(r - l + 1);
        int ans = (depth[dp[l][k]] < depth[dp[r - (1 << k) + 1][k]]) ? dp[l][k] : dp[r - (1 << k) + 1][k];
        return ans;
    }

    int lca(int x, int y) {
        x = first[x], y = first[y];
        if (x > y) swap(x, y);
        return vr[RMQ(x, y)];
    }

    int dis(int x, int y) {
        return depth[first[x]] + depth[first[y]] - 2 * depth[first[lca(x, y)]];
    }
};
int main(){
//dfs(1, 0);
//ST(Lca.tot);
}
相关标签: 算法模板