树链剖分

[Ir1d]

https://oi-wiki.org/graph/heavy-light-decomposition/

[see3p00]

完整代码第81行是不是错了呀。。函数名应该是querymax吧

[JellyGoat]

请问剖分一次时间复杂度是多少

[ouuan]

“剖分一次”难道不是指剖分过程吗？是 O(n) 的。

[Donny-Hikari]

dfs1, 第8行if内忘记更新u.hson.size

[ouuan]

dfs1, 第8行if内忘记更新u.hson.size

u.hson 是一个节点。可以理解成：

struct Node
{
    int size;
    Node* hson;
};

然后 u.hson.size 就是 u->hson->size。

[Donny-Hikari]

dfs1, 第8行if内忘记更新u.hson.size

u.hson 是一个节点。可以理解成：

struct Node
{
    int size;
    Node* hson;
};

然后 u.hson.size 就是 u->hson->size。

好的xp 和我的习惯不一样get错了

[YOURLEGEND]

dfs1的代码有问题，如果dep[1] = 0的话，那么就会导致在遍历其邻点时（以2号点为例），遍历2号点的所有出边，然后找到dep=0的1号点，将1号点的dep更新为2

[DBWGLX]

对的，不应该再找父节点了

[qodjf]

子树维护可以讲清楚一点吗？没看出来和树链剖分的关系。
如果意思是，对子树修改就去修改所包含的所有重链的话，那么会对应到超过O(logn)个重链吧。

我明白了。整个树链剖分只使用了一棵线段树。

[qwqAutomaton]

子树的 dfs 序是连续的，那么只用在线段树里面整体修改一次就行了

[oierniu]

建议加入带有换根操作的重链剖分

[oierniu]

例如 LOJ上的树链剖分模板题

[Cat-shao]

重边的定义是不是错了？

如果一个子树 x 的儿子 y 的大小超过了 x 的大小的二分之一，那么 y 是重儿子（ $size(y) = \dfrac{1}{2}size(x)$ ）。如果 x 的儿子中没有一个的 size 超过了 x 的二分之一，那么 x 没有重儿子。

（重边的定义如本文现在的样子“定义 重子节点 表示其子节点中子树最大的子结点。”，不影响重链剖分的时间复杂度。）

[minghu6]

+2 润色建议

1. "DFN"一词不是一个专门术语，而是作者代码里的对DFS序的变量命名方式，出现在正文的介绍里实在令人困惑，建议移除

2. 长链剖分的部分，概念介绍只需说明和重链的区别在于，重链按结点数（重量）来剖，而长链以树高（长度）来剖就可以了，突出重点而隐掉相同的部分，提高读者阅读效率

[Hszzzx]

能不能加一条“权值在边上的树链剖分”的条目？
例如 洛谷 P4315 月下“毛景树”。
如果这类题显而易见的话就当我没说。

[golitter]

dfs1中预处理第4行的for循环内有错误，少了个if(p[i] == fa[o]) continue;。我用这个做LCA，dfs2会死循环。加了这一句就过了。https://www.luogu.com.cn/paste/6ie63pde

[lzy20091001]

每一个结点记录 bottom 表示所在子树连续区间末端的结点。
子树维护中，bottom = u + siz(u)，其中 u 为子树的根。因此 bottom 无须记录。

[tymRocket]

感觉错误有点多。。。

[Stupid-Kimi]

能不能把 CF1009F 讲的详细一点呢？qwq

[plus-cat]

攻略（长链剖分优化贪心）的链接放错了。
应该是：攻略（长链剖分优化贪心）