看到各位大佬们已经把其他的东西讲的很明白了，我这个 juruo 就讲一讲最基本的树链剖分吧。
0.树剖是什么？能吃吗？
不能吃
树剖是树链剖分的简称，我们一般说的树剖其实指 重链剖分。当然，还有一种长链剖分我不会，但是据说不常用。
树链剖分能够把树剖分成许多链，这样就可以用维护区间的方式维护一棵树。
1.怎么剖分
先引入一些概念：
- 重儿子：一棵树最大的子树叫重儿子。例如这棵树中3就是1的重儿子：
![树链剖分详解&题解 P6098 【[USACO19FEB]Cow Land G】](https://cdn.luogu.com.cn/upload/image_hosting/wvcn1s57.png)
![树链剖分详解&题解 P6098 【[USACO19FEB]Cow Land G】](https://www.johngo689.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
很明显，一棵树的重儿子是唯一的。什么？有多棵子树的大小相同？那就随便选一个呗。 - 轻儿子：除了重儿子都是轻儿子。废话
- 重边：连接父亲和重儿子的边就是重边。
- 轻边：除了重边都是轻边。
- 重链：许多重边连起来就叫重链。例如：
![树链剖分详解&题解 P6098 【[USACO19FEB]Cow Land G】](https://cdn.luogu.com.cn/upload/image_hosting/sa0fpyz9.png)
这棵树里节点 ({1,3,5,6}) 可以构成一颗重链。很显然 ， 每个重链的起点一定是一个轻儿子。每个节点都属于且仅属于一条重链。
Original: https://www.cnblogs.com/ztxcsl/p/13577473.html
Author: ztxcsl
Title: 树链剖分详解&题解 P6098 【[USACO19FEB]Cow Land G】
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605096/
转载文章受原作者版权保护。转载请注明原作者出处！