图论树LCA性质\(LCA(A\cupB)=LCA(LCA(A),LCA(B))\)一堆点集的LCA等于其中dfn最大的和最小的点的LCAdfs序求lca好写且\(O(1)\)，吊打欧拉序和倍增。如果两个点\(x\)和\(y\)不存在祖孙关系，那么\(LCA(x,y)=fa(min(dfn_x,dfn_y))\)。我们钦定\(dfn_x<

由于是在树上搞的ds所以考察数据结构本身性质偏多，需大力注重细节。思想考虑将一颗树的链划分成若干个区间进行维护。这种划分方式叫做剖分。约束一颗有根树（有时要求换根但不是真正换根）每个点恰好包含在一条剖出的链中（若被多条链同时包含则需要同时维护多条链，修改多余

树链剖分的思想及能解决的问题树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。树链剖分（树剖/链剖）有多种形式，如重链剖分，长链剖分和用于Link/cutTree的剖分（有时被称作「实链剖

思想我先给出一些定义:定义一个结点的重子节点为其子节点中子树节点数最大的子节点，如有多个，随便取一个作为重儿子，如果没有子节点，就没有重儿子。定义一个结点的轻子节点为其除重子节点外的子节点。从这个节点到重子节点的边为重边，到其他子节点的边为轻边。由重边首位相连的链

具体见OI-wiki，下面是一些补充重链要求是极大的每个点都在某一个重链中，如果一个点是重子节点，那么其在与其父亲所连的边的重链中，否则在与其重子节点所连的边的重链中这一段的原因：我们走重链是不用关心的，因为同一重链的dfs序是连续的，我们可以用其他数据结构维护，我们只用关心这条

这条数据看起来是描述一个抗体-抗原复合物（来自PDB的6BKD结构）的详细信息，包括链的编号、序列、CDR区域等。以下是对每个字段的详细解释：总体结构pdb:"6bkd"PDBID，是一个四位字母代码，用于标识蛋白质数据库（PDB）中的一个特定的结构。这条数据描述的是PDBID为6bkd的结构。he

https://loj.ac/p/6669赛时做法先\(n-1\)次问出深度逐层考虑。slv(vector<int>a,vector<int>b)表示在点集\(a\)中寻找\(b\)中点的父亲，询问\(a[0]\)和\(b\)中所有点的距离分治下去复杂度不会算，印象中过了树剖oiwiki二叉树：最多只有一个轻儿子类似「即时战略」

定义把树剖成一条条不相交的链，对树的操作就转化成了对链的操作概念重儿子：对于每一个非叶子节点，它的儿子中以那个儿子为根的子树节点数最大的儿子为该节点的重儿子轻儿子：对于每一个非叶子节点，它的儿子中非重儿子的剩下所有儿子即为轻儿子重边：连接任意两个重儿子的边叫做重

lca目前主要是树剖求。不断跳到重链顶点的父亲，是\(O(\log(n))\)的时间复杂度，但实际比倍增跑得快很多。在求lca的过程中可以顺便把两点间的距离求出来，需要提前预处理len=点到重链顶点的长度。lca在树上差分用处大。下面是一些例题。P3128[USACO15DEC]MaxFlowP树

引言第一次接触树链/重链剖分的时候还是学习\(Lca\),没系统性的看过剖分,今天刚重新学习了一下,还是比较神奇的,没想到一个树形结构能有这么多种神奇的操作,总的来说,树链剖分还是比较重要的一个策略正文定义先给出图示首先我们给出以下几个定义:重儿子,对于一个

长链剖分字面意思，不同于重链剖分，每次选取最长的树链进行剖分，直到剖完为止。其原理和重链剖分相似。建议学习长链剖分前，先学习重链剖分。重链剖分能做的，长链剖分都能做（当然不包括找重儿子），长链剖分还能以\(O(nlogn)-O(1)\)的优秀复杂度找到\(k\)级祖先（当前节点的第\(k\)个

7.1lxlDSDay1题解P7124[Ynoi2008]stcm性质1：考虑轻儿子的子树和为\(O(nlogn)\)。证明：考虑每个结点会对多少个轻祖先做贡献，也就是重链个数，考虑每个节点到根节点重链条数为\(O(nlogn)\)，所以子树和为\(O(nlogn)\)。所以对于一条重链，如果我们已经插入了链头的补集，

引入——最大权独立集问题：最大权独立集：对于一棵树，求出一个点集，这个点集里面的任意两个点都不相连。那么在所有这样的点集中，点权和最大的那个点集，就被成为最大权独立集。想要求出最大权独立集的点权和，我们只需要使用树上dp的方法即可实现设数组f[N][2]其中f[x][0]表示不选择

树链剖分：可以把路径分割成\(logn\)个区间。概念：重/轻儿子：当前节点的子节点中子树最大的子结点称为该节点的重儿子，其余都为轻儿子重/轻边：当前节点到重儿子的边称为重边，到轻儿子的边称为轻边重链：由重边构成的极大路径->区间问题好解决，考虑序列化，链不就变成区间了

树链剖分将整棵树可以铺到线性的去维护，于是利用线段树等可维护线性数组的数据结构，就可以做到很多事情了当然也包括省赛的J题--奇偶最小生成树，并且线段树还支持修改操作，这是ST表与普通倍增维护做不到的这是没有模数的代码：intn,m;llw[N];inthead[N],cnt;structE

基本概念将树中的点重新编号,使得树中任意一条路径,都可以转化成O(logn)段连续区间1.将一棵树转化成一个序列2.将树中的任意一段路径转化成logn段连续区间(线段树,树状数组)重链剖分重儿子:子树数量最多的根节点(只有一个,多个都是,任选一个即可)轻儿子:其余儿子重边:重儿

前情提要，我主要看的是这位大佬的讲解，用的是谷的代码，所以会有点奇怪大概就是这么个意思dfs1用来处理树的dfs序，处理出重链大小和对应的重儿子voiddfs1(intnow){ son[now]=-1; siz[now]=1; for(inti=head[now];i;i=edge[i].from){ intto=edge[i].to; if(dep[to])c

树链剖分额一个怎么说感觉很鸡肋的东西，它似乎就是普通线段树加上了个路径上的修改和查询（暂时所学），但是肯定比线段树灵活。不多说，先看成果：：：如何处理树上一个点到另一个点链上的操作？如果考虑暴力的话，肯定是不可行的，因为当这个树变成类似一条链的时候，我们的复杂度就可能被卡到惊人

CF207C3GamewithTwoTrees妙到家的树上字符串问题。约定树\(1\)：\(t_1\)。树\(2\)：\(t_2\)。\(S_{1/2}(i,l)\)为树\(1/2\)上节点\(i\)沿父亲走经过\(l\)​条边所构成的字符串。\(E_{1/2}(u,v)\)为树\(1/2\)上，连接节点\(u,v\)​的边的字符。\(fa_{

树链剖分在DFS树上把连续的一段有祖先关系的单独开一个序列存储。查询每一个位置,不断地往链头条,然后跳到链头的父亲的链上\(\dots\)如果按DFS徐直接搞,会被以下数据hack可行的序列有\(:[110],[2,10],[3,12],[4,13],[5,14],[6,15],[7,16],[8,17],

染色给定一棵\(n\)个节点的无根树，共有\(m\)个操作，操作分为两种：将节点\(a\)到节点\(b\)的路径上的所有点（包括\(a\)和\(b\)）都染成颜色\(c\)。询问节点\(a\)到节点\(b\)的路径上的颜色段数量。颜色段的定义是极长的连续相同颜色被认为是一段。例如112221由

link1link2前言：树链剖分实际上就是一种将树形结构剖分成一条条链状结构，并用线性数据结构来快速维护信息。重链剖分：一些定义：重儿子：一个节点的重儿子定义为它的子节点中子树节点最大的节点。轻儿子：一个节点除重儿子外的所有儿子重边：一个节点到它的重儿子的边即为重边

树链剖分求lca参考资料：https://www.cnblogs.com/cangT-Tlan/p/8846408.html[树链剖分lca]大佬讲的很清楚%%%orz这篇博客是我的学习笔记。树链剖分：树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结

一、重链剖分1.定义&作用树链剖分用于解决在树上执行的操作，将树上操作变为区间操作。用区间来维护。2.主要思想&实现有一棵树然后，我们把边区分一下，有一些边是“重边”，其余的是“轻边”，像这样：（红边为重边，黑边为轻）重边和轻边如何确定呢？看每一个结点旁的红色数字，代表他

Part.1引入重链剖分是一种用于解决树上的路径查询和修改问题的算法，他能将\(O(n)\)级别的操作转换为\(O(\logn)\)的级别，可以说十分常用。本文将带你深入解析这个算法。Part.2概念和思路在讲解本算法之前，我们先引入一些概念：轻重儿子：对于一个树上的节点\(u\)，其儿子中子