CF传送门AT传送门两题主要Trick相同。CF的还多了一个小trick。给定一棵根节点为\(1\)的二叉树\(T\)，你需要先保留一个包含\(1\)号节点的连通块，然后给每个点确定一个权值\(a_i\)，使得对于每个点\(u\)都有其权值\(a_u\)大于等于其所有儿子的权值和\(\suma_v[(u,

全局平衡二叉树(GBST)小记以下全局平衡二叉树简称\(\text{GBST(GlobelBalancedSearchTree)}\)。我认识的大多数人，对\(\text{GBST}\)的理解基本上都是静态\(\text{LCT}\)，或者静态\(\text{TopTree}\)，不过我对\(\text{LCT}\)的理解可能还差一点，所以我不打算从阉割\(

树链剖分重链剖分【问题引入】问题描述给定一颗有$n$个节点、带边权的树，现在有对树进行$m$个操作，操作有$2$类：将节点$a$到节点$b$路径上所有边权的值都改为$c$；询问节点$a$到节点$b$路径上的最大边权值。请你写一个程序依次完成这$m$个操作。有三个操作

先挂一张jijidawang的图所以学这玩意就是被TopTree薄纱的有人把这玩意叫静态的LCT，然而可能只需要一些LCT的知识，并不需要会LCT。起码我不会注意这叫GBT，不叫GPT，能聊天的那个是CatGPT，不是CatGBT。前置知识：树链剖分用途\(O(\logn)\)处理树上链修改、链查询、子树修改、子树查

CF213ETwoPermutations考虑枚举\(x\)，我们每次就只考虑值在\([1+x,n+x]\)的数单独拿出来，看他们是否与\(a_i+x\)相同即可。具体实现时，我们可以通过一棵平衡树来快速插入和删除一个数，并用Hash来维护序列信息。CF961Fk-substrings串的中心不会改变，所以答案总的改变量不

树链剖分分为重链剖分和长链剖分以及其他奇怪的剖分。以重剖为主。重链剖分将树上问题重链剖分为序列问题（经常是DFS序）然后用数据结构（经常是线段树）维护。剖分部分定义：重儿子：对于一个点，其儿子中，子树最大的那个；重边：父亲到重儿子的连边；轻儿子：除了重儿子以外的儿子；轻边：父亲

图论树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_{