树上数据结构——ART 分解的艺术
省流：这篇文章将介绍一种名为“ART 分解”的技巧，并阐释其两个不同的应用（较复杂的一种附有代码）。ART 分解这玩意有很多长得都差不多复杂度分析也都大差不差的写法，网上看到有细节差异的话十分正常，这里介绍我个人所采用的一种。
前置体系：WRM。不过不知道也不影响，反正既然不知道那平时应该都在用。
- 什么是 ART 分解？
给定
- ART 分解的点数上有没有什么性质？
十分显然小树至多
- ART 分解有什么用？
取
它真正擅长的是：
以下我们通过两个例子来展示 ART 分解是如何工作的。
- LA
简单来说就是多次给定
由于不能保证所有读者都会长剖那一套所以简单介绍一下：对于每个节点维护其最深的儿子，这样会把树剖分成若干条链（和重剖差不多）。然后我们对每条这样剖出来的长链向上延长一倍，等于是额外维护链的一堆祖先。现在假设我们要求
现在我们考虑把它稍微优化一下。我们注意到，实际上我们只需要解决
那接下来就可以上 ART 了。我们发现把上面那个做法丢给大树直接秒了。而对于小树，它的大小是
upd on 2024.10.16：上面那个写的时候脑子不好，实际上括号序的种类数十分有限，即使带上 LA 的两个参数实际情况数也很少，可以直接预处理，不用叠层了。
于是我们就做完了。
我们考虑上面那个问题里为什么 ART 看起来非常舒适。核心原因是，复杂度瓶颈被给到了叶子数量。那如果复杂度就是只能依赖在
让我们来看看大树出问题的核心在哪里：节点太多。但它的叶子节点明明很少，这启示我们，树里有很多度为 1 的点。我们考虑，如果一个点只有一个儿子，那它和它的儿子，甚至再往下儿子，其实构成了树上的一条链，它可以和链顶链爹的边被压缩到单一条上。这需要我们写一个链上的数据结构来维护这部分的贡献。处理完之后我们的大树点数就下来了，可以正常搞了。但说起来容易做起来阴间，这个链上的数据结构需要处理长度为
这引出了我们的第二道例题。
- 树上 UFDS
简单来说就是支持两种操作：连接一个点与它的父亲，以及查询一个点沿着被连上的边能走到的最高父亲。本质是一个给定最终合并结构的并查集。
老规矩 ART，大树裸 UFDS 就是对的，记得路径压缩（不会的话可以参考代码）。由于感觉可能部分读者对并查集的复杂度不甚清晰，这里给出分析。UFDS 的复杂度在
至于小树，我们搜出每个点的 dfs 序，初始设定所有点和父亲断边（压在一个二进制状态里）。每次连边的时候只要把点在 dfs 序上的位置所对应的状态位置为 1 即可。另外维护每个点所有祖先在二进制状态里的位置，每次查询就把两个东西按位与然后取最高位即可。
而链分块后也相当好处理：块内直接二进制压每个点和前一个点的连通性，块间裸 UFDS，即可。
很显然这几个部分拼起来听着都已经不是很阳间了，于是 ut 跑去实现了一下，文末附代码。跑得挺慢的。
总而言之，ART 分解好玩捏。
class UFDS_SMALL {
private:
constexpr static int W = 6;
using ull = unsigned long long;
ull st;
vector<int> dfn, pos;
vector<ull> anc;
vector<vector<int>> es;
public:
UFDS_SMALL() {}
explicit UFDS_SMALL(int n) { init(n); }
void init(int n) {
dfn.resize(n), anc.resize(n), pos.resize(n), es.resize(n);
st = (n == (1 << W) ? 0 : (1ull << n)) - 1;
}
void add_edge(int u, int v) { es[u].push_back(v), es[v].push_back(u); }
void build(int s) {
int tot = 0;
anc[s] = 1;
function<void(int, int)> dfs = [&tot, &dfs, this](int x, int fa) {
pos[tot] = x, dfn[x] = tot++;
for (int y : es[x])
if (y != fa) anc[y] = anc[x] | 1ull << tot, dfs(y, x);
};
dfs(s, -1);
}
void link(int x) { st ^= 1ull << dfn[x]; }
int findf(int x) const {
ull s = anc[x] & st;
return s ? pos[__lg(s)] : -1;
}
};
class UFDS_BIG {
private:
vector<int> fa, msk;
int findp(int x) {
while (fa[x] >= 0) {
int f = fa[fa[x]];
if (f >= 0) fa[x] = f;
x = fa[x];
}
return x;
}
public:
UFDS_BIG() {}
explicit UFDS_BIG(int n) { init(n); }
void init(int n) {
fa = vector<int>(n, -1), msk.reserve(n);
for (int i = 0; i < n; ++i) msk.push_back(i);
}
void link(int u, int v) {
if (fa[u = findp(u)] > fa[v = findp(v)]) swap(u, v), swap(msk[u], msk[v]);
fa[v] += fa[u], fa[u] = v;
}
int findf(int x) { return msk[findp(x)]; }
};
class UFDS_LINE {
private:
constexpr static int W = 6, S = (1 << W) - 1;
using ull = unsigned long long;
vector<ull> st;
UFDS_BIG ufds;
static ull shr(int x) { return (++(x &= S) <= S ? (1ull << x) : 0) - 1; }
public:
UFDS_LINE() {}
UFDS_LINE(int n) { init(n); }
void init(int n) {
int h = ((n - 1) >> W) + 1;
st = vector<ull>(h, -1), ufds.init(h);
st[h - 1] = shr(n - 1);
}
void link(int x) {
int z = x & S, b = x >> W;
if (!(st[b] ^= 1ull << z) && b) ufds.link(b, b - 1);
}
int findf(int x) {
int b = x >> W;
ull s = st[b] & shr(x);
if (!s && b) s = st[b = ufds.findf(b - 1)];
return s ? b << W | __lg(s) : -1;
}
int findr() { return findf((st.size() << W) - 1); }
};
class UFDS_TREE {
private:
constexpr static int W = 6, S = 1 << W;
using ull = unsigned long long;
vector<int> sz, fa;
vector<vector<int>> es;
vector<pair<int, int>> bel;
vector<variant<UFDS_SMALL, UFDS_LINE>> st;
vector<vector<int>> pos;
vector<int> ufid, ufps;
UFDS_BIG ufds;
public:
UFDS_TREE() {}
explicit UFDS_TREE(int n) { init(n); }
void init(int n) {
bel.resize(n), st.resize(n), es.resize(n);
fa.resize(n), sz.resize(n), ufid.resize(n), pos.resize(n);
}
void add_edge(int u, int v) { es[u].push_back(v), es[v].push_back(u); }
void build(int s) {
vector<int> rts;
function<void(int)> dfs = [&rts, &s, &dfs, this](int x) {
sz[x] = 1;
for (int y : es[x]) erase(es[y], fa[y] = x), dfs(y), sz[x] += sz[y];
if (x != s && sz[x] <= S) return;
vector<int> tmp;
tmp.reserve(es[x].size());
for (int y : es[x])
if (sz[y] <= S)
rts.push_back(y);
else
tmp.push_back(y);
es[x] = tmp;
};
dfs(s);
for (int z : rts) {
int tot = 0;
function<void(int)> dfs = [&tot, &z, &dfs, this](int x) {
bel[x] = {z, tot++}, pos[z].push_back(x);
for (int y : es[x]) dfs(y);
};
dfs(z), st[z] = UFDS_SMALL(tot);
dfs = [&z, &dfs, this](int x) {
for (int y : es[x])
get<UFDS_SMALL>(st[z]).add_edge(bel[x].second, bel[y].second), dfs(y);
};
dfs(z), get<UFDS_SMALL>(st[z]).build(0);
}
int tot = 0;
dfs = [&tot, &dfs, this](int x) {
ufid[x] = tot++, ufps.push_back(x);
for (int y : es[x]) {
int z = y, c = 0;
while (es[z].size() == 1u)
bel[z] = {y, c++}, pos[y].push_back(z), z = es[z][0];
bel[z] = {y, c++}, pos[y].push_back(z);
st[y] = UFDS_LINE(c), es[y] = es[z], dfs(y);
}
};
bel[s] = {s, 0}, st[s] = UFDS_LINE(1), pos[s] = {s};
sz[s] = S + 1, dfs(s), ufds.init(tot);
}
int findf(int x) {
auto [rt, id] = bel[x];
if (sz[x] <= S) {
int y = get<UFDS_SMALL>(st[rt]).findf(id);
if (~y) return pos[rt][y];
x = fa[rt], tie(rt, id) = bel[x];
}
int y = get<UFDS_LINE>(st[rt]).findf(id);
if (~y) return pos[rt][y];
x = ufps[ufds.findf(ufid[bel[fa[rt]].first])];
return pos[x][get<UFDS_LINE>(st[x]).findr()];
}
void link(int x) {
auto [rt, id] = bel[x];
if (sz[x] <= S) return get<UFDS_SMALL>(st[rt]).link(id);
get<UFDS_LINE>(st[rt]).link(id);
if (!~get<UFDS_LINE>(st[rt]).findr())
ufds.link(ufid[rt], ufid[bel[fa[rt]].first]);
}
};