【摘要】本文内容部分参考这篇博客，但图片，代码均为原创 树链剖分 定义 树链剖分是一种将树按轻重边划分成若干条链，使任意两点路径可在 \(O(log\,n)\) 条链内分解，并可用线段树等结构维护路径或子树的算法。 它通过两次 DFS 求出重儿子、链顶、DFS 序等信息，从而把树上操作转化为序列区间操作，实 阅读全文