树链剖分讲解版[TAT]

我们看两个奇怪的链接,一个说很高端复杂,一个说低端简单 不过说些高端复杂的那个真的写的不错,基本上我的树链剖分是它教的!【也问了一些人了!】

树链剖分告诉我们能在链上做的大体上可以在树上做!【如果树变形的话我们可以有LCT or ETT 这个以后填坑】
问题:如果一个东西可以在树上做,是否可以在图上做呢?【我不知道】
首先树链剖分可以解决两种情况
1.点的一些相关问题:
QTREE3SDOI2011
2.边的一些问题
QTREEZJOI2011

最近看到一道BC上面用平衡树搞的树链剖分题
BC29-1004 同题提交地址HDU5173
然后我还没有写TAT

贡献一点我写了的代码 QTREE3 QTREE SDOI2011染色

对于边的做法我们是直接把它丢到父边里面去搞
对于点的做法我们也是把它丢到自己的父边里面去搞

我决定出一道杂糅题 把点和边什么都搞到一起作为练习题吧!支持修改的情况下维护一下点权sum,min,max 边权sum,min,max【这个就是树链剖分SB题了一点意义都没有纯属练手】
然后我自己搞了一道练手题没有事的人可以看一下啊
我的练手题是搞了边的,据说ZJOI有一道点的姊妹题【挖坑】
但感觉这个没意思!
我觉得链上可以玩的这个也可搞一搞 判断一条路径是否是一个 1~len[长度] 的排列 这个还是不错的吧!
然后我又想了想一条链(区间)上还可以做什么有意思的事情【欢迎回复】
然后我再想一想,感觉树链剖分就变成了 剖分+平衡树、堆、线段树

【唔sad一道树链剖分写错后的故事】
哎,其实也没有写错了!只是不会维护一个子树内的信息!
比如我们要查询一颗子树内的东西。
我们考虑剖分时特殊的dfs序。
我们维护一条链式利用了这个dfs序的特殊性【同一条链是连在一起的】
但是我们并未利用这个dfs序的一般性!什么一般性?
dfs序中的一段是对应的子树中的一部分
所以在线段树中的那一部分就是连起来的
处理子树就记录个标记就好了!善意!
所以我们来一道题目吧!

想起前面这些都是轻重路径剖分!
然后还有一个最长链剖分!听说是

Recent Posts

comments powered by Disqus