将树上区间问题转化为log N个区间问题。
定义：把点划分到链里面去，一般不包含折着的链条，一般是根节点向下，或者是祖先向下。
剖分类型：长链剖分、重链剖分。剖分就是每个节点找一个儿子连下去，然后就不会形成分叉，就是链条；其余用虚线连接。长链剖分是找最深的儿子，重链剖分是size最大的。
性质：经过轻边，子树大小翻倍。最多经过logn条轻边，logn段重边，每一段有很多条。
剖分步骤：第一次dfs找出节点的父亲、重儿子、深度、大小。第二次dfs标记时间戳，当前借点所在的重链的头是谁，头的头是自己。
(树剖LCA/板子)
维护最短路径和，最短路径加，子树和，子树加。
维护树上单点改值，路径求和，路径上最大权值。
好久没写线段树了，le,ri,s,t值赋反了。
细节：一般线段树下标是a的下标，直接赋值a[i]即可。树剖里，线段树下标是dfn值，不能直接摆a[l]，应该赋值a[id[i]]。id[i]保存的是dfn值为 i 的节点。给线段树相关函数传值时，传入的le,ri也不是下标，而是dfn，其他照旧写。
树剖+线段树。维护区间左右边的值，段数。合并顺序。
合并过程要注意顺序，[le…ri] <- 线段树上查到的 + [le…ri] <- 现在的.非常的怪，但这是有迹可循的，线段树的下标是dfn，重链是连续的dfn，[l[top[v]],l[v]]区间内是连续的，为一条重链。如果u,v没有在一条链上，下一个查询的区间就是[l[top[fa[top[v]]]],l[fa[top[v]]]]，这是下一条链的dfn区间.区间内一定是连续的，但是这两个区间在线段树上不一定连续，但一定 l[fa[top[v]]] < l[top[v]]，也就是下一个区间在当前区间的左边。区间有左右顺序，而维护内容跟区间左右又相关，自然要按照上述的规则合并。
查到最后会变成"八"字形，左边或者右边高一点，高出来的部分是找到的公共链。会变成[ri…le] + [le…ri]，任意翻转一个区间变成 [ri…le] + [ri…le] 或者 [le…ri] + [le…ri] 再合并最后一次即可。
树剖+线段树。维护区间最大值，加法tag。
树剖+线段树。维护区间个数。
一开始写错了，写成modify(u, id[r[u]], 1);了，这是改一条路径上的值。正确写法就是modify(l[u], r[u], 1, n, 1, 1);，直接把其子树全部改掉。
SP6779 GSS7 - Can you answer these queries VII
树剖+线段树。查找链上连续的最大字段和，之前有一道线段树题也是这个，只不过这题套了树剖。坑：字段可以为空(0)。这题跟染色差不多，合并要注意左右顺序。
最大子段和的求法类似于归并，(左最大后缀 + 右最大前缀) 或者 (左最大子段值) 或者 (右最大子段值)，三者取最大。settag时，如果是正数，val内所有元素应该等于区间总和。