Vani告诉我的,做个笔记,以免忘了。
同时有修改子树、修改路径、查询子树、查询路径的题目:
先树链剖分,然后dfs序,dfs时候先dfs重链的那个儿子,这样每条重链在dfs序上也是连续一段。
这样子树在dfs序上还是一个区间,而路径可以拆成log条重链,在dfs序上对应log个区间
这样就同时支持上述四个操作了。
「こんなきれいな星も、やっぱりここまで来てから、見れたのだと思うから。だから・・もっと遠くへ・・」
Vani告诉我的,做个笔记,以免忘了。
同时有修改子树、修改路径、查询子树、查询路径的题目:
先树链剖分,然后dfs序,dfs时候先dfs重链的那个儿子,这样每条重链在dfs序上也是连续一段。
这样子树在dfs序上还是一个区间,而路径可以拆成log条重链,在dfs序上对应log个区间
这样就同时支持上述四个操作了。