树链剖分是一种将一颗树通过划分不相交的来维护树上路径信息的算法。它保证每一个点仅在一个链上，并通过毒瘤数据结构来维护节点信息。
树链剖分是干什么用的呢？很简单，借助树链剖分，可以任意修改树上两点最短路径的点权和子树点权，根本用不着树上差分。
如果这棵树是一条链，支持修改和查询，那么我们可以重新按深度编号，这样子每棵子树上的编号都是连续的了，就可以用毒瘤数据结构来解决。
但是，事实上，连洛谷模板的样例都不是一条链。尽管有人说可以用LCA+树上差分过，但你觉得数据可能是纯随机的么qwq。
所以说，我们应该用树链剖分。
前置技能
第一个是刚才标粗的毒瘤数据结构，树链剖分是依靠毒瘤数据结构，比如线段树，树状数组，平衡树等来修改和查询，否则就GG了……
第二个是LCA，即最近公共祖先。
第三个是树的DFS序，这个有什么用后面会讲。