概述
-
长链剖分通过对 DP 状态的复用，有效地降低某些状态具备显著继承性的 tree dp（多为与当前子树深度有关的 dp 状态）的转移复杂度。
-
也可以说这是把本质不同的 dp 状态压到了一起。
实现原理
-
我们举最典型的能被长剖优化的 dp。
-
状态：\(dp_{i,dep}\) 表示考虑了以 \(i\) 为根的子树中，以 \(i\) 为参考时深度 \(\leqslant\) 或 \(=dep\) 的点的某个价值/...。这里为了方便写转移式我们取 \(=\)。
-
转移：\(dp_{i,dep}=(\sum/\prod/\max/\min/...\ dp_{j,dep-1})+/-/\times/...\ x\)，其中 \(j\in sons_i\)，\(x\) 为节点 \(i\) 本身的贡献之类的。
-
-
注意到，这个式子很像是把整个 \(dp_j\) “向右平移一格”了之后“摞”到一起的结果。
-
但是数组平移很烦诶。我们能不能 \(O(1)\) 地平移？我说，可以！
-
首先我们对树进行一个长剖，然后按 DFS 序来做这个 DP。
-
和我共长链的一个儿子：可以用巧妙的方式来继承过来。仔细想一想，假设我的 \(dp_i\) 的 \(dep\) 从 \(1\) 开始，那我如果勒令我的长儿子的 \(dep\) 把 \(2\) 作为开头指针，那我岂不白嫖？
-
不共长链的虚边儿子：暴力转移。注意，每次走虚边，都需要开一个“截然不同”的开头指针，这个开头指针是在空内存段上的，即，是在最后一个结尾指针的后边，否则各个重链的答案会混到一起。
-
OK，那我们来考虑一下复杂度。显然 \(i\) 本身的修改是 \(O(1)\) 的。
-
每个长链，只有在对应内存段被填满之后，才需要暴力继承。显然这一暴力的复杂度就是 \(O(len)\)，\(len\) 为长链长度，毕竟长度就是 \(dep_{max}\)。
-
这一次继承之后，就可以认为这个长链被合并到了那个更大的长链里；以后有什么贡献都是那个大长链的。
-
综上所述，复杂度为 \(O(n)\)。妙绝！
例题
进击的 95
-
题意：
-
\(n\) 个点的无边权树，\(m\) 组询问，每组询问问的是被包含于 \(S(x,d)\) 的集合构成的集族的元素个数。
-
其中 \(S(x,d)\) 表示的是以 \(x\) 为根的子树内到 \(x\) 距离不超过 \(d\) 的点的集合。
-
-
数据范围：\(n,m\leqslant 10^6,5s\)。
-
容易看出这个东西具有递推性，如果定义 \(dp_{i,d}\) 为 \(S(i,d)\) 对应的答案的话，显然有如下转移式：\(dp_{i,d}=min(mxdep_i,d)+1+\sum\limits_{j\in sons_i} dp_{j,d-1}\)。
-
其中 \(mxdep_i\) 指的是孤立考虑当前子树时，最深的点的深度（认为 \(dep_i=0\)），也可以说是当前子树内到 \(i\) 最远的点到 \(i\) 的距离。
-
显然后面的和式可以用长链剖优化。
-
但是看一下前面这个东西，仔细观察发现它具有典型的一次函数性质（如果我们把 \(dep_i\) 定义为 \(1\) 的话，只要把 \(min\) 的第二项换成 \(d+1\)，这就是个严格正比例函数）。问题是，怎么 \(O(1)\) 地做这个？
-
感觉可做（参考奇怪的函数），但关键是长链剖本身的空间分配还导致我们是依次给 \(e-1\sim e,e-2\sim e,\dots,s\sim e\) 加一次函数...暴力合并倒是好做，直接对函数求值然后把函数删了就好。
-
可是 \(1e6\)，而且 \(5s\)。
-
那谁写那个麻烦的东西啊。起开，上线段树！
-
用线段树维护差分意义下的 \(dp\) 数组。于是加一次函数就是区间修改，取值就是求前缀和。\(O(m\log n)\)。
-
其实这里可以偷个懒：一般的差分要在作用范围结束之后把影响减掉，可是我们有 \(s,e\)，而且每次加一定是一直加到 \(e\)，所以可以不去减那个影响，然后把前缀和换成从 \(s\) 开始的前缀和。
-
另外，我们这里可以在暴力的时候把对应 \(dp\) 取出来并改为 \(0\)，然后甚至可以空间复用。
-
就是常数很大，极限数据要跑 \(2s\) 出头。不过这个写法很好写，很漂亮。
-
部分代码展示：
int s[maxn],e[maxn],thee;
//每个点在 dp 中的起/止指针；dp 的内存已经被用到了哪里。请注意朴素 dp 的下标从 0 开始。
il void dfs2(int now){
if(longs[now]){
s[longs[now]]=s[now]+1,e[longs[now]]=e[now];
dfs2(longs[now]);
}
for(ri int i=hd[now];i;i=nxt[i])
if(to[i]!=longs[now]){
s[to[i]]=thee+1,e[to[i]]=thee+mxdep[to[i]]-dep[to[i]]+1;
thee+=mxdep[to[i]]-dep[to[i]]+1;
dfs2(to[i]);
for(ri int j=s[to[i]],del=1;j<=e[to[i]];++j,++del)//del 是相对当前点来说的。
ins(1,1,n,s[now]+del,get(1,1,n,j));
thee=s[to[i]]-1;
}
rev(1,1,n,s[now],e[now],1);
for(ri query qn:q[now]) ans[qn.id]=qsum(1,1,n,s[now],min(e[now],s[now]+qn.v));
return;
}
il void work(){
s[1]=thee+1,e[1]=thee+mxdep[1]-dep[1]+1;
thee+=mxdep[1]-dep[1]+1,dfs2(1);
For(i,1,m) wth(ans[i]);
return;
}
-
\(longs\) 长儿子。\(ins\) 和 \(rev\) 略，\(get\) 就是单点取值，然后改成 \(0\) 的操作。
-
这里把询问挂在点上处理了，毕竟长剖优化本身就是会破坏信息的，只能离线。
-
那个空间复用我感觉可以被卡但不完全能卡...菊花图下相当于空间 \(O(1)\)，一般图的情况，我感觉不会太好，但应该有兜底。不过不重要，随手写一下而已。
P1600 [NOIP2016 提高组] 天天爱跑步
-
题意略。
-
显然我们可以把每个人跑的路程强行拆成上行/下行两段，可以分别长剖优化。
-
对于上行，其开始时间一定是 \(0\)，故相当于一个朴素长剖。
-
对于下行，其可能是拐弯拐过来的，此时复杂度不太对：
-
dp 数组并不是只会用到 \(dep\) 以内的地方。此时需要用 u_map 优化。
-
之所以这么做复杂度是对的，是因为开出的点有限...假了。
-
好吧。看来我是假做法过的题。对于下行，我们需要重剖，然后在重剖的链上用长剖优化。复杂度证明为每个插入操作最多被合并 \(\log\) 次。
-
-
总复杂度 \(O((n+m)\log n)\)，求 lca+合并。
-
可以做到更优的复杂度：使用全局偏移+差分。
-
回忆我们在 \(\text{P2414 [NOI2011] 阿狸的打字机}\) 中的欧拉环游序做法：
-
对于深度为 \(k\) 的点，\(cnt_{t+k}\) 为第 \(t\) 秒时经过它的人数（具体的看上下行情况来决定）。
-
那么，只要我们这样赋值，并且这样取值，就对...
-
然而不对。考虑一种情况，\(son_1\) 对 \(cnt\) 的修改，可能会被 \(son_2\) 认为是自己的答案。
-
在阿狸的打字机中，我们的办法是 dfs 退出时即退栈，删去影响。然而这里我们的问题是子树性的，只需要一条链在生效的美好兴致不存在咯！
-
解决办法：差分。在进入子树的时候记录桶的情况，退出时的 \(cnt-rec\) 就是答案。它们是增量，而实质就是子树内的量。
-
时空双炸？啊...哈哈。我们只关心 \(w_{now}\) 对应点那里的啊，记录一个就行了。
-
-
合并复杂度没了，但是...我不会 \(O(n+Q)\) 的求 lca（需要树分块），所以...还是 \(O(n\log n)\)。