题目链接
rmq求lca,interesting。
一直没有学这玩意儿是因为ctsc的day1t2,当时我打的树剖lca 65分,gxb打的rmq lca 45分。。。
不过rmq理论复杂度还是小一点的,就学一下把。
rmq求lca
我们要用到三个数组
$dfn[i]$:第$i$个节点位置的时间戳
$id[i][j]$:在欧拉序中$i$到$i + 2^j – 1$这段区间内深度最小的节点编号
$dep[i]$:第$i$个节点的深度
实际上用到了一个性质:
对于任意两点的$lca$,一定是它们欧拉序中两点之间的最小值
欧拉序是什么?就是把dfs中遍历到每一个一个节点(包括回溯时遍历到)加到一个序列里,最终得到的就是欧拉序
时空复杂度
设$t = 2 * n – 1$
时间复杂度:
预处理:$o(tlogt)$
查询:$o(1)$
空间复杂度:
考虑欧拉序中有多少个点,首先每个点被访问到的时候会做出$1$的贡献
其次在遍历每条边时会多出$1$的共贡献
因此总空间复杂度为:$o(t)$
// luogu-judger-enable-o2 #include<bits/stdc++.h> const int maxn = 1e6 + 10; using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, q, s, tot, dfn[maxn], rev[maxn], dep[maxn], id[maxn][21], lg2[maxn], rd[maxn]; vector<int> v[maxn]; void dfs(int x, int fa) { dfn[x] = ++tot; dep[x] = dep[fa] + 1; id[tot][0] = x; for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == fa) continue; dfs(to, x); id[++tot][0] = x; } } void rmq() { for(int i = 2; i <= tot; i++) lg2[i] = lg2[i >> 1] + 1; for(int j = 1; j <= 20; j++) { for(int i = 1; (i + (1 << j) - 1) <= tot; i++) { int r = i + (1 << (j - 1)); id[i][j] = dep[id[i][j - 1]] < dep[id[r][j - 1]] ? id[i][j - 1] : id[r][j - 1]; } } } int query(int l, int r) { if(l > r) swap(l, r); int k = lg2[r - l + 1]; return dep[id[l][k]] < dep[id[r - (1 << k) + 1][k]] ? id[l][k] : id[r - (1 << k) + 1][k]; } int main() { freopen("a.in", "r", stdin); n = read(); q = read(); s = read(); for(int i = 1; i <= n - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dfs(s, 0); rmq(); while(q--) { int x = read(), y = read(); printf("%dn", query(dfn[x], dfn[y])); } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607572.html