树链剖分___步骤
一.按照dfs序 将点重新标号.
首先,我们要理解,为什么一定要按dfs序来标号,因为,树链剖分要操作的是一棵树上,改变两个点之间最小路上边的数据,主要是因为,每一条找到的最短路,他们点的dfs序,都可以拆成几段连续的数值,所以我们可以联想到线段树,当然这是后面的步骤;每一条最短路既然都可以用这个dfs序来分解,所以就用dfs序来给点重新编号,这里用一个id数组,表示用dfs标号后的每个点的位置.
然后就可以对它这棵树,剖分成几条链.所以进行下一步操作.
二.按照重新标号后的编号,再继续将整棵树剖分成若干条链.
其实,在dfs序之后,就可以对整棵树变成,几条单位链,也就可以对任意的两个点之间的最短路进行组合,也就是剖分组合.
然后就可以引入几个量:
重儿子,重边,重链,链顶
然后就又是一遍dfs,带上的参数,为当前的链顶和当前所到的点.然后对它进行拆解.拆解之后,每个点都属于一条链,然后对于之后每个点的操作就会有很大的用处.
三.插入操作
待续...