zhiyangfan @ 2021-12-11 10:02:11
我知道我的行为很↑↓，您们可以开骂（
思路是求两个点路径上深度最小值对应的结点
#include <set>
#include <cstdio>
#include <algorithm>
#define Ls(x) (node[x].ch[0])
#define Rs(x) (node[x].ch[1])
#define Fa(x) (node[x].fa)
const int N = 5e5 + 10;
struct Splay{ int ch[2], fa, revTag, mn, rmn, size; }node[N];
inline void pushup(int x)
{
node[x].size = (Ls(x) ? node[Ls(x)].size : 0) + (Rs(x) ? node[Rs(x)].size : 0) + 1;
if (node[Ls(node[Ls(x)].mn)].size < node[Ls(node[Rs(x)].mn)].size) node[x].mn = node[Ls(x)].mn;
else node[x].mn = node[Rs(x)].mn;
if (node[Rs(node[Ls(x)].rmn)].size < node[Rs(node[Rs(x)].rmn)].size) node[x].rmn = node[Ls(x)].rmn;
else node[x].rmn = node[Rs(x)].rmn;
if (node[Ls(x)].size < node[Ls(node[x].mn)].size) node[x].mn = x;
if (node[Rs(x)].size < node[Rs(node[x].rmn)].size) node[x].rmn = x;
}
inline void reverse(int x) { std::swap(Ls(x), Rs(x)); std::swap(node[x].mn, node[x].rmn); node[x].revTag ^= 1; }
inline void pushdown(int x)
{
if (!node[x].revTag) return ;
if (Ls(x)) reverse(Ls(x));
if (Rs(x)) reverse(Rs(x));
node[x].revTag = 0;
}
inline int get(int x) { return Rs(Fa(x)) == x; }
inline int nRoot(int x) { return Ls(Fa(x)) == x || Rs(Fa(x)) == x; }
inline void rotate(int x)
{
int fa = Fa(x), gf = Fa(fa), d = get(x), dd = get(fa);
if (nRoot(fa)) node[gf].ch[dd] = x;
node[fa].ch[d] = node[x].ch[d ^ 1]; Fa(node[x].ch[d ^ 1]) = fa;
node[x].ch[d ^ 1] = fa; Fa(fa) = x; Fa(x) = gf;
pushup(fa); pushup(x);
}
int st[N], tp;
inline void splay(int x)
{
int y = st[tp = 1] = x;
while (nRoot(y)) st[++tp] = y = Fa(y);
while (tp) pushdown(st[tp--]);
for (; nRoot(x); rotate(x))
if (nRoot(Fa(x))) rotate(get(x) == get(Fa(x)) ? Fa(x) : x);
pushup(x);
}
inline void access(int x)
{
int y = 0;
while (x) splay(x), Rs(x) = y, pushup(x), x = Fa(y = x);
}
inline void makeroot(int x) { splay(x); access(x); reverse(x); }
inline void split(int x, int y) { makeroot(x); access(y); splay(y); }
inline void link(int x, int y) { split(x, y); Fa(x) = y; }
int main()
{
int n, m, s; scanf("%d%d%d", &n, &m, &s); node[0].size = 2e9;
for (int i = 1, x, y; i < n; ++i) scanf("%d%d", &x, &y), link(x, y);
makeroot(s);
for (int i = 1, x, y; i <= m; ++i)
{
scanf("%d%d", &x, &y); split(x, y);
printf("%d\n", node[y].mn);
}
return 0;
}by jerry3128 @ 2021-12-11 10:03:37
这是什么惊恐实现方式。
by zhiyangfan @ 2021-12-11 10:04:13
刚刚板子打错了，改过了，虽然还是错（
#include <set>
#include <cstdio>
#include <algorithm>
#define Ls(x) (node[x].ch[0])
#define Rs(x) (node[x].ch[1])
#define Fa(x) (node[x].fa)
const int N = 5e5 + 10;
struct Splay{ int ch[2], fa, revTag, mn, rmn, size; }node[N];
inline void pushup(int x)
{
node[x].size = (Ls(x) ? node[Ls(x)].size : 0) + (Rs(x) ? node[Rs(x)].size : 0) + 1;
if (node[Ls(node[Ls(x)].mn)].size < node[Ls(node[Rs(x)].mn)].size) node[x].mn = node[Ls(x)].mn;
else node[x].mn = node[Rs(x)].mn;
if (node[Rs(node[Ls(x)].rmn)].size < node[Rs(node[Rs(x)].rmn)].size) node[x].rmn = node[Ls(x)].rmn;
else node[x].rmn = node[Rs(x)].rmn;
if (node[Ls(x)].size < node[Ls(node[x].mn)].size) node[x].mn = x;
if (node[Rs(x)].size < node[Rs(node[x].rmn)].size) node[x].rmn = x;
}
inline void reverse(int x) { std::swap(Ls(x), Rs(x)); std::swap(node[x].mn, node[x].rmn); node[x].revTag ^= 1; }
inline void pushdown(int x)
{
if (!node[x].revTag) return ;
if (Ls(x)) reverse(Ls(x));
if (Rs(x)) reverse(Rs(x));
node[x].revTag = 0;
}
inline int get(int x) { return Rs(Fa(x)) == x; }
inline int nRoot(int x) { return Ls(Fa(x)) == x || Rs(Fa(x)) == x; }
inline void rotate(int x)
{
int fa = Fa(x), gf = Fa(fa), d = get(x), dd = get(fa);
if (nRoot(fa)) node[gf].ch[dd] = x;
node[fa].ch[d] = node[x].ch[d ^ 1]; Fa(node[x].ch[d ^ 1]) = fa;
node[x].ch[d ^ 1] = fa; Fa(fa) = x; Fa(x) = gf;
pushup(fa); pushup(x);
}
int st[N], tp;
inline void splay(int x)
{
int y = st[tp = 1] = x;
while (nRoot(y)) st[++tp] = y = Fa(y);
while (tp) pushdown(st[tp--]);
for (; nRoot(x); rotate(x))
if (nRoot(Fa(x))) rotate(get(x) == get(Fa(x)) ? Fa(x) : x);
pushup(x);
}
inline void access(int x)
{
int y = 0;
while (x) splay(x), Rs(x) = y, pushup(x), x = Fa(y = x);
}
inline void makeroot(int x) { access(x); splay(x); reverse(x); }
inline void split(int x, int y) { makeroot(x); access(y); splay(y); }
inline void link(int x, int y) { split(x, y); Fa(x) = y; }
int main()
{
int n, m, s; scanf("%d%d%d", &n, &m, &s); node[0].size = 2e9;
for (int i = 1, x, y; i < n; ++i) scanf("%d%d", &x, &y), link(x, y);
makeroot(s);
for (int i = 1, x, y; i <= m; ++i)
{
scanf("%d%d", &x, &y); split(x, y);
printf("%d\n", node[y].mn);
}
return 0;
}by WZKQWQ @ 2021-12-11 10:06:02
惊人的实现方式
by XL4453 @ 2021-12-11 10:06:32
惊恐。
by zhiyangfan @ 2021-12-11 10:06:41
/jk/jk 发生什么事了
by jerry3128 @ 2021-12-11 10:09:35
@zhiyangfan 我先问一问你的目的是求 LCA 还是练习链上信息的维护（LCA 不是两次 Access 来求得嘛（
by zhiyangfan @ 2021-12-11 10:11:19
@jerry3128 链上信息的维护（
但是两次 access 求 LCA 确实不会（
by jerry3128 @ 2021-12-11 10:14:23
@zhiyangfan 你维护的是一个节点子结构相对于根的深度。但是在 split 函数中你调用了换根函数。
by Lynkcat @ 2021-12-11 10:15:31
根都换了/jk
by zhiyangfan @ 2021-12-11 10:16:22
/jk/jk 我是↑↓