Splay树,或伸展树，是一种平衡二叉查找树，它通过Splay/伸展操作不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，能够在均摊O(\logN)时间内完成插入，查找和删除操作，并且保持平衡而不至于退化为链。Splay树由DanielSleator和RobertTarjan于1985年发明

定义圆方树：将无向图转化为树形结构的数据结构，使得树上2点路径上的点都是原图的必经点。圆点：原无向图\(G\)中的点，仍然保留在圆方树中，称之为圆点。方点：将每一个点双连通分量新建一个“方点”。树边：每一个方点都向对应的点双内的圆点连边。基本性质：性质一：圆方树的总点数=

简介LCT是常用的一种动态树。对于一般的树上问题，我们会用树剖解决，但是如果遇到动态增删边的问题就需要LCT来解决。LCT的本质上是一种链剖分，我们将所有的边剖分为虚边和实边，所以整棵树是由若干条实链构成的，实链之间用虚边相连。我们通过splay来维护实链的信息，并以从上到下

原题链接题解给定若干条路径限制，问是否合法对于树上任意三个点\(a,b,c\)（不一定直接相连），如果已知\(a\oplusb,b\oplusc\)那么\(a\oplusc\)也已知所以我们可以对限制里相连的节点放到一个集合里，并且统一记录他们到集合头领的路径异或值由于奇数个1异或偶数个1之间的异

概念引入最近公共祖先简称\(LCA\)（LowestCommonAncestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。在下面的说明中，我们设两个节点分别为\(x\),\(y\)，节点\(x\),\(y\)的深度分别表示为\(dep_x\),\(dep_y\),将树称为\(T\)算法详解:朴素算法：

先抛出一个问题：给一个有向图，问从\(1\)节点出发，求每个节点的受支配集。这里，支配的定义为：若从\(1\)结点出发到\(v\)节点的所有路径中，都必须经过\(u\)节点，则称\(u\)支配\(v\)。那么受支配集意思就是对于\(v\)点满足条件的\(u\)点的集合。那么根据支配的定义，我们可以

原题链接题解题目要求有多少个点，其到标记点的最远距离不超过\(d\)看到这个我们不难想到树的直径：设直径端点\(a,b\)，树上任意一点\(c\)到叶子节点的距离\(\leqmax(d(c,a),d(c,b))\)所以，我们把标记点看成叶子节点，并找出相距最远的一对标记点\(ab\)，如果某点与\(a,b\)的

目录史莱姆融合松鼠接松果 新月轩就餐 史莱姆融合根据题意就是一道集合合并的题，所以要用并查集，不过最后我们要输出整个序列，所以要在合并的时候维护一个链表，以便最终合并成一个大集合的时候，输出整个链表就是答案。不过这里有一点要注意，就是我们在更新链表的时候是把

模拟赛T1挂\(70pts\)，T2\(\mathbb{AC}\)力挽狂澜，T3暴力爆零，T4\(5min=30pts\)。T1CowTollPathsG弗洛伊德，跑的过程记最大点权。注意有后效性，需要迭代一下。按点权排序后再跑可以不用迭代，因为一定会先更新小的，再更新大的。注意是：变量名别写错？？？code#include<bits/st

字符串哈希素数：13110612e6+931e7+192e7+933e7+231e9+97LL(1e16)+61Zfunctionn=strlen(s+1),m=strlen(t+1);z[1]=n;For(i,2,n,l=0,r=0){ if(i<=r)z[i]=min(z[i-l+1],r-i+1); while(s[z[i]+1]==s[i+z[i]])++z[i]; if(i+z[i]-1>

目录1从BST到平衡树2替罪羊树2.1替罪羊树的维护2.2替罪羊树的基本操作2.2.1替罪羊树的结点信息2.2.2替罪羊树的空间利用2.2.3替罪羊树的重建2.2.4替罪羊树的插入、删除2.2.5替罪羊树的按数找排名、按排名找数2.2.6替罪羊树的找前驱、后继2.3替罪羊树完整代码1从BS

Splay树感谢OI-WIKI讲解1.定义splay是一种平衡二叉搜索树，由splay操作使时间复杂度O（nlogn）2.变量rt根节点编号tot节点个数计数tr[].fa父节点编号tr[].ch[0/1]左右儿子编号tr[].val该点记录的权值tr[].cnt该点记录的权值出现次数tr[].sz子树大小intrt,tot;structnode

数据结构——并查集学习笔记并查集是一种用于管理元素所属集合的数据结构，实现为一个森林。并查集中，每棵树表示一个集合，树中的节点表示对应集合中的元素。其思想是，把集合属性绑定到根节点上，避免多余的处理，因此一般难以分离。普通并查集并查集支持两种操作：合并（Union）：合并两个元素

5-16P3934[Ynoi2016]炸脖龙I思路：先不考虑带修考虑化开式子有\(a^b=a^{b\mod\phi(p)+[b>=\phi(p)]\phi(p)}\pmodp\)那么\((l,r,p)\)可以转移到\((l+1,r,\phi(p))\)p为偶数时\(\phi(p)<p/2\)p转移一次后必为偶数（或1）那么log次后有\((l,r,1)\)显然为0细节：但

并查集扩展应用A.货物运输题目描述有\(n\)座城市和\(m\)条双向道路。已知走过每条边所需要的汽油量，\(q\)次询问，求汽油量为\(l\)的车可以在多少对城市之间运送货物。（汽车到达城市会立刻把油全部加满）题解这道题没有强制在线，所以可以考虑进行离线。对于大小为\(n\)一

P3043[USACO12JAN]BovineAllianceG并查集每个连通块方案数独立。考虑一个连通块的情况，显然如果\(m>n\)一定无解，那么就只有\(m=n\)和\(m=n-1\)两种情况，前者是基环树，后者是树。基环树的环上，第一条边选择的端点确定，其他也就确定，共有两种情况。环下的树选择固定。所有总

MyBlogsP10359[PA2024]Kolorowylas/tuu。写了三天。首先考虑树的形态不变怎么做，直接的想法是树分治这种东西可以做到一只或者两只\(\log\)。但是点分这种东西不太好扩展到动态树的问题。但是因为这是单点查询，所以可以不用真正的树上染色，只需要回答每个询问即可。考虑对于

纯唐比赛T1同类分布一眼数位DP，没啥好嗦的但是，题面出锅，本来数据范围给的是\(2^{31}\)，结果考完一看测试数据\(11000000000000000000\)，照搬洛谷就算了吧，时限还抄错（洛谷3000ms考试时1000ms）我真的*****你猜我为啥T190分#include<bits/stdc++.h>usingnamespacestd;#d

思想综述并查集（Union-Find）算法的主要操作包括两种：合并（Union）：将两个不相交的集合合并成一个集合。查询（Find）：查询两个元素是否属于同一个集合。并查集算法的核心思想是使用树（通常是森林）来表示这些不相交的集合，其中每个集合被表示为一棵树，树的根节点代表这个集合的标识（或称为代表

$\LARGE{一些无聊的定义}$二叉搜索树(BST树)定义二叉搜索树是一种二叉树的树形数据结构，其定义如下：空树是二叉搜索树。若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其

达到今日更新量题目让我们求所有简单路径上最大值减去最小值的总和实际上就是所有简单路径的最大值总和减去所有简单路径上最小值总和然后分别求所以简单路径的极值，下面以最大值为例：我刚开始想到了非常SB的做法：枚举最大值x，设比x大的数为y，实际上有很多y，如果y是x的祖先，那么点对

AC自动机用于多个模式串（模式串在文本串里面出现），和文本串匹配对模式串建立trie,每个点上维护一个fail,每个节点其实代表一个前缀。若干个模式串形成了若干个前缀字符串集合S。fail[i]表示S中的所有字符串中，能和i这个字符串的后缀完全匹配的最长字符串。(当然这个字符串不能是i

CF1039DYouAreGivenaTree树形dp+贪心+根号分治题目是一个经典问题，可以用树形dp和贪心解决。设\(f_u\)表示以\(u\)节点为端点能够剩下的最长路径。考虑从叶子节点往上合并贪心，那么如果能够合并出包含\(u\)节点的大于等于\(k\)的路径，那么就合并，\(f_u=0\)；否

一段合法的括号序和一棵有根树唯一对应，具体而言，考虑生成括号序的过程，从根节点出发，遇到左括号就向下走一步，遇到右括号就向上走一步由于树上的一个节点可能有多个子节点，因此在不规定访问顺序的情况下，同一棵树有多种不同的括号序列点击查看代码#include<bits/stdc++.h>using

CF453CLittlePonyandSummerSunCelebration生成树+构造看看一个点的奇偶性意味着什么。意味着奇数的点必须经过至少一次，而偶数不用经过。那么所有奇数的点两两路径必须构成一个连通块。然后就可以开始想构造了。考虑连通块上的任意一棵生成树，如果一个非根节点走完子树后次