树链剖分详解&题解 P6098 【[USACO19FEB]Cow Land G】

看到各位大佬们已经把其他的东西讲的很明白了，我这个 juruo 就讲一讲最基本的树链剖分吧。
0.树剖是什么？能吃吗？
不能吃
树剖是树链剖分的简称，我们一般说的树剖其实指重链剖分。当然，还有一种长链剖分我不会，但是据说不常用。
树链剖分能够把树剖分成许多链，这样就可以用维护区间的方式维护一棵树。
1.怎么剖分
先引入一些概念：
重儿子：一棵树最大的子树叫重儿子。例如这棵树中3就是1的重儿子：很明显，一棵树的重儿子是唯一的。什么？有多棵子树的大小相同？那就随便选一个呗。轻儿子：除了重儿子都是轻儿子。废话重边：连接父亲和重儿子的边就是重边。轻边：除了重边都是轻边。重链：许多重边连起来就叫重链。例如：
这棵树里节点 /(/{1,3,5,6/}/) 可以构成一颗重链。很显然 ，每个重链的起点一定是一个轻儿子。每个节点都属于且仅属于一条重链。<-很重要，一定要记住！ 然后就开始剖分了。 具体的剖分过程，就是维护一些数组： /(deep[i]/) 代表节点 /(i/) 的深度。/(top[i]/) 代表节

树链剖分详解&题解 P6098 【[USACO19FEB]Cow Land G】最先出现在Python成神之路。