与轻重链剖分相似.dfs1：高度\(h\)、\(son\)；dfs2：\(top\).性质1：到根最多\(O(\sqrtn)\)条轻边.（证明：长链长度最坏情况：1,2,3...）性质2：\(x\)的\(k\)级祖先\(y\)所在的长链长度\(\gek\).（证明：若非，则\(y-x\)是一条更长的链，矛盾.）树上\(k\)级祖先\(O(n\logn)-O(1)\)：

重链剖分第一次DFS求重儿子（子节点更多的儿子）。第二次DFS求重链剖分（先访问重儿子再访问其他轻儿子）。变量：重儿子，子树大小，DFS序（\(x\)根子树DFS序中第一次出现位置），以\(x\)为根的子树的最后一次出现位置，深度，\(x\)所在重链的顶端。voiddfs1(intx){//求出重儿子，sz[v]

闲话似乎会有很多种树剖，什么长链剖分之类的，但是暂时只会轻重链剖分（可怜）。以前的版本在这里，但是感觉写的太粗糙了，所以决定重写一篇（我也不知道为什么要一直写树剖而不写点别的）。正文引入如果给出一个序列，有一些区间修改查询之类的操作，直接上线段树什么的就完事了，但是如果给出的

概述轻重链剖分通过将树剖分为若干条重链和它们之间相连的轻边，将树上路径问题转化成序列问题。具体来讲，有很多树上路径问题本质上是把序列上的问题搬到了树上，此时我

//LuoguP3384【模板】轻重链剖分/树链剖分#include<iostream>#include<cstring>#include<algorithm>#include<vector>#definelcu<<1#definercu<<1|1usin

LCA与树上差分轻重链剖分长链剖分树分治

【模板】轻重链剖分/树链剖分题目描述如题，已知一棵包含\(N\)个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：1xyz，表示将树从\(x\)到\(y\)结点

题意:给定一棵树，nn 个结点。根为 11，所有的结点只能走向其父亲结点。有 qq 次询问，每次询问给出 33 个结点集合 A,B,CA,B,C。问树上有多少点满足如下条件：该点可以