我不会做ppt/ll
先来看一棵树：
树剖的经典问题：
两种操作，一种是将点 \(u\) 到点 \(v\) 路径上所有点加上一个值；第二种是查询路径 \(u\) 到路径 \(v\) 的点权之和。
显然，普通的树上差分已经无法解决这种问题了。
于是我们需要一种预处理来降低复杂度。
区间修改，这肯定用到线段树，但是这是一棵树，我们如何把他变成连续区间呢。
于是树剖诞生了：我们将整棵树按照重儿子（一个节点的儿子中，以其为根的子树大小是所有儿子中最大的，他就是重儿子）优先遍历，按遍历顺序将每个点打上一个序号（这就是 dfn 序)（不是重儿子的结点遍历顺序随便，如果有子树大小相同的儿子，任选一点作为重儿子），于是整棵树变成了：
所有点旁边括号内就是我给这个点标上的 dfn 序，所有与重子的连边我都打上了感叹号。
你会发现，感叹号形成了一个个链（我们称之为重链），这棵树就可以抽象成：
是挺抽象的
有意思的是一条重链上所有点的 dfn 序是连续的，于是我们就可以把这一整棵树改成一个个区间了！
然后就可以用线段树维护重链了，每次查询完，就跳一次父亲进入另一条重链。
至于复杂度证明，我们发现每查询一次重链，是 \(\log{n}\) 的，复杂度就在于我们会跳父亲，但是每跳一次父亲，子树大小就会至少翻倍，所以最多跳 \(\log{n}\) 次父亲，于是复杂度最多就是 \(\log^2{n}\)。
至于查询一个点以其为根的子树中所有点的点权的和（或者最值）这种问题，你会发现，子树中的 dfn 序是连续的，所以只用在线段树上求该点的 dfn 序到该点 dfn 序加上该子树大小再减一的区间即可。
具体讲一下实现：
先进行一次 DFS 处理出重子，深度，子树大小，每个点的父亲。
然后再进行一次 DFS 求出该点表上的序号、所在的重链的链首（就是深度最小的那个，也是序号最小的那个）即可（记得要先遍历重子，再遍历轻儿子）。
修改和查询时，两边的两个点优先跳深度大的那个，如果发现两点在同一条链上，就结束，然后修改这两个点之间的点即可（区间修改嘛，都会吧）。
线段树的实现我还讲吗……
很简单，是吧
然后上好题：
送的。
还是送的。
相信简单的边权转点权都会吧。
由于每个点只有一个父亲（【数据删除】？），所以我们把每个点到他父亲的边的边权存在这个点上就可以了（根节点为点权零哦）。
相信简单的边权转点权都会吧。
好极了，又是一道边权转点权。
只能我无语了。
好啊好啊，妙极了
再来。
应该，没了？（？）
标签：遍历,剖分,复杂度,树链,dfn,子树,重链,边权 From： https://www.cnblogs.com/Y2y7m/p/17426765.html