title ：树上问题基础tags : ACM,图论date : 2021-11-6author : Linno基本概念树的深度：从树根往下数，叶子节点所在的最大层数称为树的深度。（有教材定义不一样，看题意吧。要区分高度）树的直径：树中两节点距离的最大值称为树的直径。子树大小：对每一个节点的大小都等于左子树大小+右子树大小+1（自己）节点重量：删去该节点后，所有树大小的最大值。即该节点所有子树大小

title : 2-SATdate : 2021-10-14tags : ACM,图论author : Linno简介SAT指适定性问题，k-SAT表示k-适定性问题。可以证明k>2时，k-SAT是NP完全的，所以一般讨论k=2的情况。思想对于2-SAT问题，本质上是对NP问题的暴力求解。（1）我们可以以每一个变量及其反变量为点进行建图。若x1&x2=0,则连边方式为x1->!

title :树Hashdate ： 2021-10-6tags : ACM,图论author : Linno树哈希应用判断树是否同构思想判断无根树同构的时候，可以比较重心为根的Hash值或者比较每个点为根的Hash值。树哈希的表示方法fx=1+∑y∈sonxfy×prime(sizey)f_x=1+\sum_{y\in son_x}f_y×prime(size_y)fx​=1+∑y∈sonx​​

title : 珂朵莉树date : 2021-8-26tags : ACM,数据结构author ：Linno简介珂朵莉树(Chthlly Tree)也叫老司机树，ODT(Old Driver Tree)。只要是由区间赋值操作的数据结构都可以使用这种数据结构来骗分，在数据随机的情况下效率很高。对于add,assign和sum操作，用set实现的珂朵莉树复杂度位O(nloglogn)。问题起源[C

title : 配对堆与左偏树date : 2021-8-22tags : 数据结构,ACM配对堆简介配对堆(pairing heap)，支持插入，查询/删除最小值，合并，修改等操作，跑得比较快，但不能可持久化。操作合并直接把根节点权值较大的那个配对堆设成另一个的儿子即可。插入新元素可视为一个配对堆，与原堆合并即可。删除最小值(复杂)若把根节点的儿子都一个个合并到一起，复杂度会退化到O(n)Eil

title : 树状数组tags ： 数据结构date : 2021-7-22核心操作int lowbit(x){return x&(-x);}//你也可以写成下述形式#define lowbit(x) (x&-x)意义在于取出x最低为的1。一维树状数组单点修改+区间查询void update(int x,int y){ //将x点加上yfor(int i=x;i<=n;i+

title : 交互题tags : ACM,交互date : 2022-2-11author : Linno交互题通俗来讲，交互题与平时题目的输入输出反过来，是让你设计程序去向用户提出询问，由用户给出答案，并且在这基础上由程序推断出正确答案的一种形式。在下面第一道例题中会认识到交互题的基本写法。应用cf上的话说明怎样调整输入输出：//This is an interactive problem.

概念：Request是python中原生的一款基于网络请求的模块。特点：功能强大，简单便捷，效率极高。作用：模拟浏览器发请求。

title : 斯坦纳树tags : ACM 图论date : 2021-6-26author : Linno什么是斯坦纳树给定 nn 个点 A1,A2,⋯,AnA1,A2,⋯,An，试求连接此 nn 个点，总长最短的直线段连接系统，并且任意两点都可由系统中的直线段组成的折线连接起来。他们将此新问题称为 斯坦纳树问题。斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给

title : 后缀自动机date : 2021-11-11tags : ACM,字符串author : Linno前置知识KMP，Trie，AC自动机等字符串基础DFA（有限状态自动机）后缀自动机(Suffix automaton ,SAM)定义字符串s的SAM是一个接受s的所有后缀的最小DFA（确定性有限自动机）。直观上SAM是给定字符串的所有字串的压缩形式。而构造的时间复杂度和空间复杂度仅为