长链剖分
title: 长链剖分
categories:
- ICPC
tags:
- null
abbrlink: 478025c
date: 2023-09-14 00:00:00
长链剖分
https://blunt-axe.github.io/2019/11/25/20191125-Longest-Decomposition-Notes/
[P3899 湖南集训] 更为厉害 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
[P5904 POI2014] HOT-Hotels 加强版 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.cnblogs.com/maoyiting/p/14178833.html#/cnblog/works/article/14178833
重链剖分定义子树大小最大的为重子节点，而长链剖分定义子节点中子树 深度最大 的子节点为重子节点。如果有多个子树深度最大的子节点，取其一。如果没有子节点，就无重子节点。
性质：链的长度定义为链包含的点数
- 任意节点 p 的 k 级祖先q所在的链的长度一定大于 k
- 证明：分情况讨论。根据定义q→p 链的长度为 k+1 ，如果 p 和 q 在同一条链上，那这条链的长度自然大于 k 。如果p 和 q 不在同一条链上，设 q 所在链的链头和链尾分别是 top 和 tail ，根据长剖定义，top→q→tail 必须比 top→q→p 长，所以链的长度也大于 k 。
- 任意节点 p 到根节点最多经过 $\sqrt {n}$ 级别的轻边
- 证明：因为每经过一条轻边到一条新的链，新的链的长度一定严格大于上一条链（可以利用性质1简单证明），由于树上所有链的长度和为 n ，所以经过的链的长度形成一个和小于等于 n 的严格递增序列，当每次长度加1时序列最长，长度为 n 级别$(1+2+3+…+ \sqrt{n})$。
O(1)求k级祖先P5903 【模板】树上 K 级祖先 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
首先，我们同样进行一个树上倍增的预处理， O(nlogn) 地预处理出每个节点的 $2^k$级祖先。然后我们再对每一个链头节点 p 预处理出它的 $1,2,…,len[p]−1$ （ len[p] 为链长）级祖先节点和链上的$1,2,…,len[p]−1$ 级子孙节点。显然因为所有链的链长加起来是 n ，所以这部分是 O(n) 的。
对于每个询问，设 $2^i≤k<2^i+1 $（ k=0 时特判），考虑 p 的 $2^i$ 级祖先 q ，它所在的链的链长一定大于 $2^i。由于我们要找的是 q 的 $$k−2^i$级祖先，而 $k−2^i<2^{i+1}−2^i=2^i<len[top[q]]$ ，所以因为q在链上，q所在链的链头top的预处理了上下一倍链长，所以这个祖先它一定已经被预处理过了（要么在链上，要么是链头的小于链长级祖先），算一下差值，查询就好。
ui s;
inline ui get(ui x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return s = x;
}
void solve() {
int n, q;
cin >> n >> q >> s;
int rt = 0;
vector<int> l(n + 1), r(n + 1), node(n + 1);
int idx = 0;
vector<int> fa(n + 1), dep(n + 1);
vector<int> hson(n + 1), top(n + 1), len(n + 1);
vector<vector<int>> e(n + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x == 0) {
rt = i;
continue;
}
e[x].push_back(i);
}
auto dfs1 = [&](auto self, int u, int curd = 1) -> void {
dep[u] = curd;
len[u] = 1;
for (auto v : e[u]) {
fa[v] = u;
self(self, v, curd + 1);
if (len[v] + 1 > len[u]) {
hson[u] = v;
len[u] = len[v] + 1;
}
}
};
auto dfs2 = [&](auto self, int u, int tp) -> void {
l[u] = ++idx;
node[idx] = u;
top[u] = tp;
if (hson[u])
self(self, hson[u], tp);
for (auto v : e[u]) {
if (top[v])
continue;
self(self, v, v);
}
r[u] = idx;
};
int bei = __lg(n);
vector<vector<int>> st(bei + 1, vector<int>(n + 1));
vector<vector<int>> anc(n + 1), des(n + 1);
auto work = [&](int rt) {
dfs1(dfs1, rt);
dfs2(dfs2, rt, rt);
for (int i = 1; i <= n; i++) st[0][i] = fa[i];
for (int i = 1; i <= bei; ++i) {
for (int j = 1; j <= n; ++j) {
st[i][j] = st[i - 1][st[i - 1][j]];
}
}
for (int i = 1; i <= n; ++i) {
if (top[i] == i) {
for (int j = 0, p = i; j < len[i]; ++j, p = fa[p])
anc[i].push_back(p);
for (int j = 0; j < len[i]; ++j)
des[i].push_back(node[l[i] + j]);
}
}
};
auto query = [&](int p, int k) {
if (k == 0)
return p; // 特判
int i = __lg(k), q = st[i][p];
int tp = top[q];
// q的k-(1<<i)级祖先小于链长，预处理了两倍链长的信息
int d = k - (1 << i) - (dep[q] - dep[tp]);
if (d > 0)
return anc[tp][d];
else
return des[tp][-d];
};
int x, k;
ll res = 0;
work(rt);
ll ans = 0;
for (int i = 1; i <= q; i++) {
x = (get(s) ^ res) % n + 1;
k = (get(s) ^ res) % dep[x];
deb(x, k);
res = query(x, k);
deb(res);
ans ^= (ll)i * res;
}
cout << ans << endl;
}
#贪心「BZOJ 3252」攻略
给定点带权的点数为 n 的树，要选出 k条包含 叶子 的祖先后代链，使得它们并的点权和最大，每个点只能加一次。
Sol：考虑带权的长链剖分，剖出的链取前 k 条加起来即可。时间复杂度 $O(nlogn)$。具体来说就是由于两个叶子在lca处往上只能取一次，所以我们考虑贪心取点权和最大的一条儿子链继承，贡献就加到叶子上面。答案一定是合法的，因为有叶子一定会先取叶子的，叶子的答案肯定较大。
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<int>> e(n + 1);
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
vector<int> ans(n + 1);
vector<int> id(n + 1);
function<void(int, int)> dfs = [&](int u, int fa) {
int tmp = 0;
for (auto v : e[u]) {
if (v == fa)
continue;
dfs(v, u);
// 必须选一个叶子节点
if (ans[id[v]] + a[u] > tmp) {
tmp = ans[id[v]] + a[u];
id[u] = id[v];
}
}
// 处理叶子
if (id[u] == 0) {
id[u] = u;
ans[u] = a[u];
} else
ans[id[u]] = tmp;
};
dfs(1, 1);
deb(ans);
nth_element(ans.begin() + 1, ans.begin() + n - k + 1, ans.end());
int res = 0;
deb(ans);
for (int i = n - k + 1; i <= n; i++) res += ans[i];
cout << res << endl;
}
应用：「CF 1009F」Dominant Indices](https://codeforces.com/problemset/problem/1009/F)
题意：给定一颗1为根，n个节点的树。$f(x,i)表示x子树中距离x为i的节点数$.对于每一个点求最小值k满足$f(x,k)$最大。$1 \le n \le 1e6$
Sol：考虑暴力dp。$f[x][i]=\sum_{y \in son[x]} f[y][i-1]$.这种做法在一条链的时候会被卡死。考虑长链优化，先搜重儿子，利用指针偏移继承重儿子的答案。再暴力合并轻儿子的dp值，并更新答案。
- f数组开不下，考虑指针给每个节点动态分配内存。
- 复杂度的正确性：每个点只属于一条长链且只会在top处合并一次，实践复杂度$O(n)$
int buf[M];
int *dp[N];
int *p = buf;
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n + 1);
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
vector<int> hson(n + 1), len(n + 1);
function<void(int, int)> dfs = [&](int u, int fa) {
len[u] = 1;
for (auto v : e[u]) {
if (v == fa)
continue;
dfs(v, u);
if (len[u] < len[v] + 1) {
hson[u] = v;
len[u] = len[v] + 1;
}
}
};
dfs(1, 1);
vector<int> ans(n + 1);
function<void(int, int)> dfs2 = [&](int u, int fa) {
dp[u][0] = 1;
if (hson[u]) {
dp[hson[u]] = dp[u] + 1; // 复用重儿子，坐标偏移1
dfs2(hson[u], u);
ans[u] = ans[hson[u]] + 1; // ans[u]初始化成最大深度
}
for (auto v : e[u]) {
if (v == fa || v == hson[u])
continue;
dp[v] = p;
p += len[v]; // 轻儿子指针动态分配内存
dfs2(v, u);
for (int j = 1; j <= len[v]; j++) {
dp[u][j] += dp[v][j - 1];
if (dp[u][j] > dp[u][ans[u]])
ans[u] = j;
else if (dp[u][j] == dp[u][ans[u]] && j < ans[u]) {
ans[u] = j;
}
}
}
if (dp[u][ans[u]] == 1)
ans[u] = 0;
};
dp[1] = p;
p += len[1];
dfs2(1, 1);
for (int i = 1; i <= n; i++) cout << ans[i] << endl;
}
一道简单的树形dp，从叶子向上传递信息https://www.luogu.com.cn/problem/CF767C
题意：一棵树点权有正有负，找到两个边去除以后，树被分成三部分，三部分的点权和相等。输出一组方案。不存在输出-1
Sol：赛时做法：割两个边要输出u->v的v表示方案，记录为v1,v2。首先总和必须整除3。考虑在lca处可以统计到答案，是一个先更新答案，再合并子树的过程，所以需要保留信息向上传递。
再考虑每次把当前子树根节点合并进去的时候，会重复计算贡献，也就是为祖先关系的时候应该当前子树根是$\frac{2 sum}{3}$并且子树内部存在$\frac{sum}{3}$,从这可以看出为什么要特判0.
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n + 1);
int rt;
vector<int> a(n + 1);
int sum = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x >> a[i], sum += a[i];
if (x == 0)
rt = i;
else
e[x].push_back(i);
}
if (sum % 3) {
cout << -1 << endl;
return;
}
int tar = sum / 3;
deb(tar);
vector<int> f1(n + 1);
vector<int> mp(n + 1);
// pii ans;
vector<int> c;
function<void(int)> dfs = [&](int u) {
for (auto v : e[u]) {
deb(u, v, a[u]);
dfs(v);
// 更新答案
if (f1[v] && f1[u]) { // 两个割点的lca处统计
cout << mp[u] << " " << mp[v] << endl;
exit(0);
}
// if (a[v] == tar)这是错的，下面的答案传递不上来
// mp[u] = mp[v];
// 更新数组
if (f1[v])
mp[u] = mp[v];
f1[u] += f1[v];
a[u] += a[v];
}
if (u != rt) { // 根节点不能贡献
if (tar == 0) { // 这需要特殊判断
if (a[u] == tar && f1[u] >= 1) {
cout << u << " " << mp[u] << endl;
exit(0);
}
if (a[u] == tar) {
f1[u] += 1, mp[u] = u;
}
} else { // 两个割点成祖先关系
if (a[u] == tar)
f1[u] += 1, mp[u] = u;
if (a[u] == 2 * tar && f1[u]) {
cout << u << " " << mp[u] << endl;
exit(0);
}
}
}
};
dfs(rt);
deb(a);
cout << -1 << endl;
}
反思一种简明的写法：考虑找到合法点就一定割是对的。为了不重复计算直接dp值合法点的减去一次，不可能存在超过两个这样的点，不然就说明有好几个部分相加等于sum。除非sum为0，而sum为0，在我们减去贡献是不影响的。
void solve() {
int n;
cin >> n;
vector<vector<int>> e(n + 1);
int rt=0;
vector<int> a(n + 1);
int sum = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x >> a[i], sum += a[i];
if (x == 0)
rt = i;
else
e[x].push_back(i);
}
if (sum % 3) {
cout << -1 << endl;
return;
}
int tar = sum / 3;
int v1 = 0, v2 = 0;
auto dfs = [&](auto self, int u) -> void {
for (auto v : e[u]) {
self(self, v);
a[u] += a[v];
if (a[v] == tar) {
if (v1 == 0) {
v1 = v;
a[u] -= a[v];
} else if (v2 == 0) {
v2 = v;
a[u] -= a[v];
}
}
}
};
dfs(dfs, rt);
if (v1 && v2)
cout << v1 << " " << v2 << endl;
else
cout << -1 << endl;
}