树链剖分是一种很神奇的算法。
定义
重儿子：每个节点的儿子中子树大小最大的一个。
重边：每个节点连接到重儿子的边。
轻边：不是重边的边。
思路
首先我们找出所有重链（即重边组成的链），
然后就可以发现一个性质：从$u$点到$v$点的路径上只有不超过$O(log\ n)$条重链。
所以我们可以用线段树对每一条重链进行维护。
维护的信息多种多样：可能是每个点的权值、每个点到父亲的那条边的权值。
然后在修改、查询的时候就可以用$O(log^2\ n)$的时间操作。
例题
Codeforces 343 D
直接用线段树维护每个节点是否有水。（话说树状数组就可以了？？？
Codeforces 191 C
直接用线段树维护每个节点经过了多少次。
Codeforces 372 D
这个稍微麻烦点。
首先我们得$two\ pointers$扫包含$[l,r]$内的点。
然后就是要快速处理添加一个点到集合内并且把它链到某一个lca上面去/删除一个点并把它到某个lca的链删掉。
这玩意用树链剖分维护一下每个点选不选就好了。
Codeforces 593 D
这个用线段树维护每个点权值的区间乘积。如果超过$10^{18}$就把它设成$inf$。除的时候就直接$0$了。
话说判断的过程也是蛮有趣的。。。
UOJ 128
直接用线段树维护每个软件的安装情况就好了。
扯淡
话说LCT是个什么玩意。。。是不是就是动态的树链剖分啊。。。
其实树链剖分写起来挺短的
也就150行吧