1 ：长链剖分的构造
推荐先行学习重链剖分
与重链剖分类似，我们设一个节点中深度最深的子节点为长节点，设该节点到长节点的边为重边，其他边为轻边
然后我们把首尾相连的重边组成长链，落单的一个节点也被视作一条长链
我们就把树分成了若干条互不相交的长链
2：长链剖分的性质
- 树上所有长链长度和为n
- 互不相交，很好理解
- 节点x的k级祖先y所在长链长度必定大于等于k
- 如果小于k，节点x到节点y的长度比长链大，不符合长链定义
- 从节点x沿长链跳到根节点，跳跃次数最多为 $O(\sqrt{n})$
- 每跳一次长链，调到的长链次数会越来越大。最坏情况为1，2，...，$\sqrt{n}$。
3：树上k级祖先
如题，求x节点的树上k级祖先
显然可以倍增，也可以树剖+LCA。但用长链剖分可以做到询问$O(1)$
我们预处理出每一个节点的$2^k$级祖先（倍增）， 再处理出每一个长链顶端d的len[d]级儿子和len[d]级祖先（len[d]为以d为顶端的长链长度）
对于每一个询问，我们首先找出一个数t，使$2t<k<2{t + 1}$，然后把x往上跳$2^t$。我们的目标就变为了求现在x的$k - 2 ^ t$级祖先
根据性质2，原来x的$2t$级祖先y（也就是现在的x）所在长链长度必定大于等于$2t$。
我们又能知道$k - 2 ^ t$肯定小于$2 ^ t$。因此$k - 2 ^ t$小于当前x所在链的长度
因此把x跳到当前链的顶端，就可以用预处理出的数组$O(1)$解决
这道题输出记得要开long long，不然就会像某个憨批一样调半个小时:)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n, q;
unsigned s;
unsigned get(unsigned x)
{
x^=x<<13,x^=x>>17,x^=x<<5;
return s=x;
}
int st[maxn], nx[maxn << 1], to[maxn << 1], tot;
void add(int u, int v)
{
nx[++ tot] = st[u];
st[u] = tot;
to[tot] = v;
}
int dep[maxn], mx[maxn], son[maxn], f[maxn], dp[maxn][23];
void dfs1(int u, int fa)
{
mx[u] = dep[u] = dep[fa] + 1;
dp[u][0] = f[u] = fa;
for(int i = 1;i <= 22;i ++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
for(int i = st[u];i;i = nx[i])
{
int v = to[i];
if(v == fa) continue;
dfs1(v, u);
if(mx[v] > mx[u]) son[u] = v, mx[u] = mx[v];
}
}
int top[maxn], num[maxn], cnt, len[maxn];
void dfs2(int u, int topu)
{
top[u] = topu;
num[u] = ++ cnt;
len[u] = mx[u] - dep[topu];
if(son[u]) dfs2(son[u], topu);
for(int i = st[u];i;i = nx[i])
{
int v = to[i];
if(v == f[u] || v == son[u]) continue;
dfs2(v, v);
}
}
//以上为长链剖分的构造
vector<int> df[maxn];
vector<int> ds[maxn];
int query(int x, int d)
{
if(d == 0) return x;
int i = log(d) / log(2);
int u = x;
u = dp[u][i];
d -= (1 << i);
d -= (dep[u] - dep[top[u]]);
u = top[u];
if(d > 0) return df[u][d];
else return ds[u][-d];
}
int main()
{
scanf("%d%d%u", &n, &q, &s);
int f, rt;
for(int i = 1;i <= n;i ++)
{
scanf("%d", &f);
if(f == 0) rt = i;
else add(f, i), add(i, f);
}
for(int i = 0;i <= 22;i ++) dp[rt][i] = rt;
dfs1(rt, rt);
dfs2(rt, rt);
for(int i = 1;i <= n;i ++)
{
if(top[i] != i) continue;
int u = i;//预处理顶点数据
for(int j = 0;j <= len[i];j ++)
{
df[i].push_back(u);
u = dp[u][0];
}
u = i;
for(int j = 0;j <= len[i];j ++)
{
ds[i].push_back(u);
u = son[u];
// cout << ds[i][j] << ' ';
}
// cout << endl;
}
// cout << endl;
long long x, k, res = 0, ans = 0;
for(int i = 1;i <= q;i ++){
x = (get(s) ^ res) % n + 1;
k = (get(s) ^ res) % dep[x];
res = query(x,k);
// cout << x << ' ' << k << endl;
// cout << res << endl;
ans ^= i * res;
//
}
printf("%lld\n",ans);
return 0;
}
4：用长链剖分优化dp
题目大意：给定一棵以 1 为根，n 个节点的树。设 d(u,x)d(u,x) 为 u 子树中到 u 距离为 x 的节点数。对于每个点，求一个最小的 k，使得 d(u,k) 最大。
实际上就是把题面复制了一遍
暴力的dp很容易想，dp[i][j]为i子树中距离为j的节点数，转移dp[i][j]时将i的所有儿子的dp[son][j - 1]加到一起就行了。但这样是$O(n^2)$的
发现dp的转移只与深度有关，考虑用长链剖分优化
dfs到节点x时，我们先dfs x的长儿子，然后直接继承长儿子的dp数组
注意长儿子的深度比x多1，因此继承时要错开一位
然后dfs其他儿子，暴力dp更新
由于每一条链只会在链顶暴力dp一次，所以理论复杂度为$O(n)$
但可以想象，这么做常数巨大，有时可以比肩启发式合并
接下来稍微讲一下如何继承长儿子dp数组
显然直接暴力搞空间会炸
有一种方法是开vector，这种方法在有些题里很好用，但在另外的题里细节爆炸
这里主要讲述用指针的方法
容易看出，如果我们先遍历长儿子，那么每一条长链DFS序是连续的。因此我们可以在每一个链的顶端动态申请空间。就像这样：
int *dp[maxn], tmp[maxn], *id = tmp;
dp[y] = id;
id += len[y];
（每一次申请的空间要能容纳这一条长链。因此每次要申请链的长度这么大的空间）
空间会炸的问题解决了。由于dp数组被我们搞成了一堆指针，所以重儿子的继承只需要这样就行：
dp[son[u]] = dp[u] + 1;
这样u节点的重儿子的dp值会直接错位存入u节点中。
完整代码如下；
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e6 + 5;
ll n, x, y;
ll tot, st[maxn], to[maxn << 1], nx[maxn << 1];
void add(ll x, ll y)
{
to[++tot] = y;
nx[tot] = st[x];
st[x] = tot;
}
ll top[maxn], dep[maxn], mx[maxn], len[maxn], son[maxn], f[maxn];
void dfs1(ll u, ll fa)
{
f[u] = fa;
mx[u] = dep[u] = dep[fa] + 1;
for(ll i = st[u];i;i = nx[i])
{
ll v = to[i];
if(v == fa) continue;
dfs1(v, u);
if(mx[v] > mx[u]) son[u] = v, mx[u] = mx[v];
}
}
ll ans[maxn], *dp[maxn], tmp[maxn], *id = tmp;
void dfs2(ll u, ll topu)
{
top[u] = topu;
len[u] = mx[u] - dep[topu] + 1;
dp[u][0] = 1;
if(son[u])
{
dp[son[u]] = dp[u] + 1;
dfs2(son[u], u);
ans[u] = ans[son[u]] + 1;
}
for(ll i = st[u]; i; i = nx[i])
{
ll y = to[i];
if(y == f[u] || y == son[u]) continue;
dp[y] = id;
id += len[y];
dfs2(y, u);
for(ll j = 1; j <= len[y]; j++)
{
dp[u][j] += dp[y][j - 1];
if(dp[u][j] > dp[u][ans[u]] || (dp[u][j] == dp[u][ans[u]] && j < ans[u])) ans[u] = j;
}
}
if(dp[u][ans[u]] == 1) ans[u] = 0;
}
int main()
{
scanf("%lld", &n);
for(ll i = 1; i < n; i++)
{
scanf("%lld%lld", &x, &y);
add(x, y), add(y, x);
}
dfs1(1, 0);
dp[1] = id;
id += len[1];
dfs2(1, 0);
for(ll i = 1; i <= n; i++) printf("%lld\n", ans[i]);
return 0;
}
容易看出，如果维护的dp值只与深度有关，我们就可以试着用长链剖分优化
（这里原本还有一道题目，但被咕掉了。）
5：用长链剖分优化贪心
这一部分很神仙，题好像也比较少。如果有好题推荐请洛谷私信~
所以只放了一道例题：给定一棵树，每个点有点权，选定k个叶子，满足根到k个叶子的所有路径所覆盖的点权和最大。每个节点的权值只被计算一次
(题目来源：BZOJ3252 攻略)
考虑一个贪心：每次选择一条权值和最大的路径，统计后将路径上所有点权清零
这个贪心正确，但似乎不太好做
忽然我们发现：长链剖分是可以统计路径长度的。只要把深度改为点权和就行了
长链剖分有一个显而易见的性质：每一条长链总是会到一个叶子节点。如果不到，这条链就不是最长链了。
所以我们要做的就是选k条权值和最长的链相加就行了。
代码很简单，就不放了
6：结尾
虽然前面提到了树上启发式合并，但作者对启发式合并并不熟悉
所以有可能会再开一篇博客？但作者是个鸽子，咕了也很正常。。。
标签：长链,剖分,int,ll,maxn,节点,dp From： https://www.cnblogs.com/closureshop/p/16792644.html