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);
}