树链剖分

简单介绍

一些针对树上一条链的题目，可以通过树链剖分解决。

核心思想是将树分成若干条链，每条链建一棵线段树，对于书上一条路径的操作，
转化为对于每个链的操作。在此基础上，使得一条路径跨过的链的个数尽量少。

轻重链剖分

每个点向自己最大的子树连一条边，这样整个树可以被划分成叶子数条链。

在一些实现中，最大的子树（节点数最多）也可以被实现为叶子数最多的子树。
之后的分析没有变化。

时间复杂度

可以发现如果顺着一条非重链向上跳，那么子树大小至少乘以 $2$ 。

这样从任意一个点跳到根节点，至多需要跳 $O(\log n)$ 次，
也就是说任意两个点之间的路径至多跨过 $O(\log n)$ 个重链。
每条重链再用线段树维护，总时间复杂度为 $O(\log^2 n)$ 。

参考题目

Luogu P2146
非常好的一道题，将DFS序和树链剖分结合了起来。

bzoj 1036
树链剖分模板题。

树链剖分

把一个树划分成若干个链
每个点属于且只属于一条链
任意两点之间，路径至多经过log(n)个链
怎么划分最好？

长链，最坏情况 sqrt(n)
重链，最坏情况 log(n) 每个点计算重儿子

第一次DFS，计算出每个子树的大小

第二次DFS，生成DFS序
DFS时每到一个点，先走重儿子

P4377 [USACO18OPEN]Talent Show G

f[i] 表示重量i，最大的才艺值
最大化f[i] / i，只枚举i >= W
重量范围太大，不行

f[i] 表示才艺值i，最小的重量
最大化i / f[i]，只枚举f[i] >= W
是错误的

2 3
2 1
1 1
1 1000

01分数规划
二分最终答案
每个物品只有1种属性才艺值-重量 * 最终答案
背包，判断是否存在总重量 >= W
属性和 >= 0

P1774 最接近神的人
(2, 1)
(8, 2)
(0, 3)
(3, 4)

(0, 3)
(2, 1)
(3, 4)
(8, 2)

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100020];
int b[100020];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		b[i] = i;
	}
	sort(b + 1, b + 1 + n, [](int x, int y){return a[x] < a[y];});
	for (int i = 1; i <= n; i++)
	{
		printf("%d%c", b[i], i == n ? '\n' : ' ');
	}
}

P1396 营救
二分时，可以只二分出现过的权值

CF609E
https://codeforces.com/contest/609/submission/14889101
每个集合维护一个边集，表示边的一端在集合内，另一端在集合外

合并两个集合的时候，维护这个边集
回答边的两端在这两个集合中
路径压缩

https://codeforces.com/contest/609/submission/42482642
不路径压缩
启发式合并，得到一个树高不太大的树
在启发式合并得到的树上暴力进行询问

树链剖分
Heavy Light Decomposition

https://www.luogu.com.cn/problem/P2590
[ZJOI2008]树的统计

https://www.luogu.com.cn/problem/P2486
[SDOI2011]染色

https://www.luogu.com.cn/problem/P3178
[HAOI2015]树上操作
子树加，询问到根节点的一条链，可以用DFS序和线段树
x子树中每个点都 += y

询问x子树中每个点i的答案（从i到根节点的和） += (d[i] - d[x] + 1) * y
询问x子树中每个点i的答案（从i到根节点的和） += d[i] * y - (d[x] - 1) * y
对于每个点维护2个部分，比如a和b
a[i] += y
b[i] += (d[x] - 1) * y
最终答案是a[i] * d[i] - b[i]

子树修改，单点求值
DFS序，转化为单点修改，区间求和

链加，子树求和，可以用DFS序和线段树

x到根节点每个点i都 += y

询问x到根节点每个点i的答案（点i子树的和） += (d[x] - d[i] + 1) * y
询问x到根节点每个点i的答案（点i子树的和） += (d[x] + 1) * y - d[i] * y

对于每个点维护2个部分，比如a和b
a[i] += y
b[i] += (d[x] + 1) * y
最终答案是b[i] - a[i] * d[i]

链修改，单点求值
DFS序，转化为单点修改，区间求和

4个问题