长链剖分小计 - 洛谷保存站

## 长链剖分

将重链剖分中的重儿子（siz最大的儿子）变为长儿子（dep最
大的儿子），来将树划分成一条条不交的链。常常用于优化与深度有关的树上 dp/计数 问题。

### 基本性质：

- 任意不同长链不交（都是树链剖分了）。
- 从任意一点出发到根的路径上经过的短边不超过 $O(\sqrt n)$。证明考虑每次跳短边后子树内所有点的siz和，卡得最满就是 $1+2+3+4+5+ \dots$。（siz $\ge$ 链长）总和不超过 $n$，所以项数是 $O(\sqrt n)$ 的。注意次结论对**带边权**的树并不使用(~~虽然好像不带权树也从没用过就是了~~)。
### 常用的基本步骤：

- 找长儿子，预处理深度等信息。
- 将树剖分成若干长链。
- 解决问题，一般分为两步：继承长儿子信息与合并短儿子信息。

主播的马蜂：

```cpp
void dfs_pre(int u){
	for(int v:E[u])if(v^fa[u])
		mxdep[v]=dep[v]=dep[fa[v]=u]+1,dfs_pre(v),mxdep[v]>mxdep[u]&&(mxdep[u]=mxdep[son[u]=v]);
}
```
找长儿子。

```cpp
void dfs_path(int u,int tp){
	F[u]=F[0]++;
	if(son[u])dfs_path(son[u],tp);
	else {
		int *s=G[0];
		for(int v=u;v!=fa[tp];v=fa[v])G[v]=G[0]++;
		G[0]+=(G[0]-s);
	}
	for(int v:E[u])if(v!=fa[u]&&v!=son[u])dfs_path(v,v);
}
```
划分长链，并为数组标号（F,G 都是指针数组，主播习惯提前分配好内存地址）

```cpp
void dfs_solve(int u){
	for(int v:E[u])if(v^fa[u])dfs_solve(v);++F[u][0];ans+=G[u][0];
	for(int v:E[u])if(v!=fa[u]&&v!=son[u]){
		for(int x=1;x<=mxdep[v]-dep[v];++x)ans+=F[u][x-1]*G[v][x];
		for(int x=0;x<=mxdep[v]-dep[v];++x)ans+=G[u][x+1]*F[v][x];
		for(int x=1;x<=mxdep[v]-dep[v];++x)G[u][x-1]+=G[v][x];
		for(int x=0;x<=mxdep[v]-dep[v];++x)G[u][x+1]+=F[u][x+1]*F[v][x],F[u][x+1]+=F[v][x];
	}
}
```
继承长儿子信息，并合并短儿子信息。

上述代码均出自 [P5904](https://www.luogu.com.cn/problem/P5904)。

### part 1 经典问题：树上k级祖先

[P5903 【模板】树上 K 级祖先](https://www.luogu.com.cn/problem/P5903)

省流： $O(n\log n)$ 预处理 $O(1)$ 查，总复杂度 $O(n\log n +q)$。实际表现因为数组调用太慢，跑不过重链剖分 $O(n +q\log n)$。

用到了长剖的另一性质：任意一个点的 $k$ 级祖先所在长链的长度 $\ge k$（这个应该很显然）。

记 $len_u$ 表示 $u$ 所在长链的长度。

考虑长剖之后对于每条链的链顶 $u$ 记录自其向上的 $1,2,3,\dots len_u$ 级祖先，以及从链顶向下的 $0,1,2,\dots len_u$ 级长儿子。这部分复杂度 $O(n)$。

考虑当前要求点 $u$ 的 $k$ 级祖先，考虑将 $k$ 拆成 $k=x+y(x\ge y)$。我们先跳到 $u$ 的 $x$ 级祖先 $v$，然后获取 $v$ 的链顶 $top_v$，然后判断 $v$ 的 $y$ 级祖先在 $top_v$ 上方还是下方，两种情况分别用记录下的祖先信息与长儿子信息即可实现 $O(1)$ 查询。

现在问题变为如何 $O(1)$ 跳到 $u$ 的 $x$ 级祖先（满足 $x\ge \frac{k}{2}$），考虑若 $x$ 取```1<<__lg(k)```可以满足，于是对于每个点预处理出向上跳祖先的倍增数组，这部分 $O(n\log n)$。

---

### part 2 长链剖分宝宝题

### [CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F)

- 继承长儿子的信息，等价于数组下标上的平移，可以用指针实现。
- 暴力合并短儿子的信息。因为每条长链最多被其链顶的父亲合并一次，所以总复杂度 $O(n)$。

### [P3565 [POI 2014] HOT-Hotels](https://www.luogu.com.cn/problem/P3565) & [加强版](https://www.luogu.com.cn/problem/P5904)

考虑在 $3$ 个点的 $lca$ 处统计贡献。

记 $F[u][x]$ 表示在 $u$ 子树内且 $dist(u,v)=x$ 的 $v$ 的点的数量。

记 $G[u][k]$ 表示在 $u$ 子树内的二元组 $(x,y)$ 的数量，满足 $dep_x=dep_y ~ \land ~ 2 \times dist(x,lca(x,y)) -dist(x,u)= k$。维护这个的目的比较显然，因为要找到一个点 $v$ 满足 $v$ 与 $x$ 在 $u$ 的不同子树中，满足 $dist(v,lca(x,y))=dist(x,lca(x,y))$，容易发现此时 $dist(v,u)= k $。

发现  $F$ 与 $G$ 都可以通过继承长儿子信息与合并短儿子信息维护，同时答案也可以通过二者求出。

#### 维护 F

- 继承长儿子的信息。
- 暴力合并短儿子的信息。

#### 维护 G

数组的平移方向与 $F$ 相反。

#### 维护答案

记当前点为 $u$,当前合并的短儿子为 $v$。

- 考虑用当前已经合并进 $u$ 的子树对应深度的二元组与 $v$ 子树中对应深度的点更新答案。
-  考虑用当前已经合并进 $u$ 的子树对应深度的点与 $v$ 子树中对应深度的二元组更新答案。
-  每次要先统计答案，再合并 $F$ 与 $G$ 的信息。

#### 细节

$G$ 的对应内存池要开 $2$ 倍大小（不然会越）。

#### 核心代码
```cpp
void dfs_path(int u,int tp){
	F[u]=F[0]++;//分配 F
	if(son[u])dfs_path(son[u],tp);
	else {
		int *s=G[0];
		for(int v=u;v!=fa[tp];v=fa[v])G[v]=G[0]++;
		G[0]+=(G[0]-s);
    //分配G，注意G的内存池开2倍。
	}
	for(int v:E[u])if(v!=fa[u]&&v!=son[u])dfs_path(v,v);
}

void dfs_solve(int u){
	for(int v:E[u])if(v^fa[u])dfs_solve(v);++F[u][0];ans+=G[u][0];
	for(int v:E[u])if(v!=fa[u]&&v!=son[u]){
		for(int x=1;x<=mxdep[v]-dep[v];++x)ans+=F[u][x-1]*G[v][x];
		for(int x=0;x<=mxdep[v]-dep[v];++x)ans+=G[u][x+1]*F[v][x];
		for(int x=1;x<=mxdep[v]-dep[v];++x)G[u][x-1]+=G[v][x];
		for(int x=0;x<=mxdep[v]-dep[v];++x)G[u][x+1]+=F[u][x+1]*F[v][x],F[u][x+1]+=F[v][x];
	}
}
```

### [P7581 「RdOI R2」路径权值(distance)](https://www.luogu.com.cn/problem/P7581)

维护每个点子树中对应“距离”（经过边数）的出现次数与实际深度和。合并与计算答案是简单的。注意当询问的 $k\ge mxdep_u-dep_u$ 时答案为 $0$（直接查询会越界到其他地方，致使答案出错）。

时间复杂度 $O(n)$。

### [P3899 [湖南集训] 更为厉害](https://www.luogu.com.cn/problem/P3899)

当 $b$ 是 $a$ 的祖先的贡献情况是平凡的。

考虑 $b$ 为 $a$ 子树内的节点，我们对于每个 $a$ 维护答案，实现 $O(1)$ 查询。

记 $F[u][x]$ 表示 $v$ 在 $u$ 子树内且 $dist(v,u)=x$ 的 $v$ 的权值(即 $siz_v-1$)和。

查询时都需要快速获取 $F[u]$ 的前缀和。

考虑直接维护前缀和。每次暴力后缀加复杂度不可接受，不妨转为全局加，前缀减。继承长儿子与合并短儿子时都这样，复杂度就 $O(n)$ 了。

也需要注意查询时越界的问题。

### [P10641 BZOJ3252 攻略](https://www.luogu.com.cn/problem/P10641) & [CF958B2 Maximum Control (medium)](https://www.luogu.com.cn/problem/CF958B2)

考虑“长剖”然后记每条长链的贡献。前者 ```nth_element``` 可以做到 $O(n)$。后者要以直径端点为根。证明不太会。

### [CF504E Misha and LCP on Tree](https://www.luogu.com.cn/problem/CF504E) & [P9399 「DBOI」Round 1 人生如树](https://www.luogu.com.cn/problem/P9399)

考虑维护根链的正反哈希值，使用可以支持快速合并/分裂的多项式哈希（CF要写双模）。每次二分长度，获取哈希值简单分讨+树上 $k$ 级祖先即可。长剖理论复杂度 $O((n+q)\log n)$。不过应该跑不过重剖 $O(q\log^2 n)$。

### part 3 长链剖分入门题

### [CF860E Arkady and a Nobody-men](https://www.luogu.com.cn/problem/CF860E)

重剖 $O(n\log^2 n)$ 可以一眼，但长剖 $O(n)$ 真的好想吗？

转长剖并维护前缀和后，问题变为如下：

- 对一个集合内的位置都加上某个值。
- 合并两个集合。
- 所有操作之后询问每个位置的值，保证每个位置最多出现在一个集合中。

可以考虑建出森林，合并集合就是合并两棵树，用类似建kruskal 重构树的方式建，最后下传标记即可。

### [20250603联考T1 和谐点对](https://oj7.top/problem/1554)

考虑任意一个三元组都可以产生 $2$ 的贡献，对于一个三叉结构，若存在相等的 $dist(u,center)$ 则可能有额外的贡献。

- 等等等，每个 $4$ 的额外贡献。
- 长长短，没有额外贡献。
- 长短短，每个会有 $2$ 的额外贡献。

等等等的情况是

正在渲染内容...