定义1：删去该点后最大子树最小的点定义2：删去该点后所有子树大小均不超过n/2的点两个定义是等价的。如果一个点有超过n/2的子树，那么往这个方向走一步，其最大子树会变小。性质：一棵树最多有2个重心且相邻重心到所有点距离和最小可以用调整法证明（相当于换根），P2986[USACO1

重心与起重作业的关系重心就是物体分割成许多微小体积的重力的合力中心。重心与起重作业的安全关系重大，在起重安全施工规范中明确地规定：吊钩作用线与重物的重心必须在同一条垂直线上。物体的重心位置是进行起重施工所必须掌握的重要技术数据之一。重心与起重作业的关

什么是树的重心？树上选取一个点，使得最大的子树大小最小的点叫做重心。重心有很多优美的性质，求重心是容易的，不再阐述。1.以重心为树根时，最大的子树的大小不超过全树大小的一半，同时条件是充要的对于充分性：考虑调整法。不妨现在钦定一个重心\(u\)作为树根，有一个儿子\(v\)且

括号树题意：给定一棵树，以\(1\)为根，每个点有字符(或)。定义\(s_i\)为\(i\)到根的路径的子串中合法括号序列的个数，求\(\bigoplus_{i=1}^ni\timess_i\)，\(1\len\le5\times10^5\)。记\(p_i\)为\(i\)的父亲，\(a_i\)为\(i\)到根的路径以\(i\)结尾的合法括

A好数（number）开桶记录。BSOS字符串（sos）\(f_{i,j,k,n}\)表示到\(i\)，结尾两个字母是\(j,k\)，已经有了\(0/1/2\)个SOS，字母有\(4\)类，分别为O，没用过的S，无用字母X，用过的S，的方案数，转移暴力。C集训营的气球（balloon）首先有暴力背包，然后每次修改看成删除一个，添加一个，就成退

多校A层冲刺NOIP2024模拟赛05T1好数（number）签到题首先\(O(nV)\)的背包暴力是显然的，注意到本题只需要合法性，状态只有\(0/1\)，上\(bitset\)优化转移即可。时间复杂度\(O(\frac{nV}{w})\)。T2SOS字符串（sos）签到题计数题难点在不重不漏，而本题则主要是不重。考虑一种好的

二分答案P2824排序有时候可以尝试二分最后的答案，把不好维护的东西变成\(0\)和\(1\)。操作分块P5443桥梁将操作分块维护，一般适用于可以很好维护静态询问但是需要支持修改的情况（？）。状态压缩去除后效性P2157学校食堂dp有后效性但影响范围很小可以考虑把后续决策压缩起

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

###思路1.使用DFS遍历树，计算每个节点的子树大小。2.计算每个节点的最大连通块大小。3.找到最大连通块大小最小的节点，即为树的重心。###伪代码1.读取输入数据，构建树的邻接表。2.定义DFS函数，计算每个节点的子树大小。3.遍历所有节点，计算每个节点的最大连通块大小

树的重心性质：一个点是重心，等价于，以这个点为根，它的每个子树的大小，都不会超过整个树大小的一半（充要条件）性质及其证明POJ3107模板这题卡vector注意判断数组越界voiddfs(inti,intfa){ siz[i]=1; inttmp=0; for(intj=head[i];~j;j=e[j].next){ intv=e[j].to; if(v!

A\(n\)个人之间有若干认识关系，你要把这些人划分为两个集合，使得集合里的每个人都认识偶数个人。求方案数，\(n\le1000\)。设每个人的状态为\(0/1\)表示两个集合，那么第\(i\)个人在其集合里认识的人个数是\(\sum_{j}(x_i\otimesx_j\otimes1)\)。解这个方程，高斯消元，若自由

欢迎来看“片”（的简介）由于-\(看片\)-生涯转瞬即逝，于是我选择对“\(片\)”进行一定的总结：相信你一定看懂了由于开始的时间有一点晚，就姑且认为我以后会慢慢补充吧......回到总部点分治\(P4178\)\(Tree\)解：树的重心，树上\(DFS\)搜索，点分治经过（两）天(一)夜的鏖战，总算\(\m

树的直径定义：树上最长的简单路径。（可能有多条）树的直径的性质直径两端点一定是两个叶子节点。距离任意点最远的点一定是直径的一个端点，这个基于贪心求直径方法的正确性可以得出。对于两棵树，如果第一棵树直径两端点为(u,v)，第二棵树直径两端点为\((x,y)\)，用条边将两棵树

树的重心当\(u\)作为根时，其节点数最大的子树最小，则称\(u\)为树的重心。性质一：节点数最大的子树的节点数不超过\(\frac{节点总数}{2}\)。（反证法，若某重心\(u\)的节点数最大的子树的节点数超过\(\frac{节点总数}{2}\)，则将其一个子节点提起来会更优）性质二：至多两个且一

2024暑假集训总结知识点清单：树状数组拓展：（1）k维前缀和（2）树状数组+倍增没码过，小慌线段树：（1）线段树不仅仅是一个维护区间和、区间最值或者类似于方差那道题，维护区间的平方等等信息，它的深层是将区间拆分为\(O(logn)\)个子区间从而将修改与查询降为\(O(logn)\)级别，因此对于线

前言还真没有。点分树点分树是个神秘的东西。点分树是通过更改原树形态使树的层数变为稳定\(\logn\)的一种重构树。常用于解决与树原形态无关的带修改问题。是这样的，有些树上问题，看起来用别的树形结构做不了，点分治能做。但是它不仅多次询问（\(n\)同级），还带修，有时候甚至

图像的质心，也称为图像的重心。重心的概念可以参考如下的杠杆示意图，即杠杆重心两端的质量相等。 扩展到图像上面，图像中每一点的像素值可以理解成此点处的质量。不同之处是图像是2维的，解决的方法是在x方向和y方向上分别独立地找出质心。即对于x方向的质心，图像在质心左右两边像素

无根树分治一般常见于树上路径问题(计数,最优化等).常见题目如无权树树上距离为k(对1到n-1求)的路径数量.点分黑白且可以改,求两端都是黑点的最远路径.以我的理解,三种分治都是无法互相平替的,对于每种分治我尝试给出一道只能用这个分治的题目.三种分治复杂度均为logn*T(n).

k-means算法把相似的数据汇总为簇的方法叫作聚类。k-means算法是一种聚类算法，该算法非常简单，所以被广泛应用于数据分析。概述k-means算法是一种有代表性的聚类算法。由于该算法简单易懂，又可以用于比较大的数据集，所以在市场分析和计算机视觉等领域得到了广泛的应用。我

练字要领1.比对，要通过对字的每一笔进行比对，才能逐渐进步（成年人写字有定势思维）2.提升书写速度，理解行笔路径，可以虚化路径，流畅的使用路径就可以提升书写速度。3.笔锋的控制，通过对笔的提按来控制粗细；刚开始是方向的控制。4.一行字的对齐的方式，三种类型：正方形，扁形，宽形；把字的重心放

P7903兜心の顶题目背景Source：八仙敬酒吕洞宾——醉酒提壶力千钧；铁拐李——旋肘膝撞醉还真；汉钟离——跌步抱坛兜心顶；蓝采和——单提敬酒拦腰破；张果老——醉酒抛杯踢连环；曹国舅——仙人敬酒锁喉扣；韩湘子——擒腕击胸醉吹箫；何仙姑——弹腰献酒醉荡步。题目描述给定正

点分治对于一棵子树，即正常dfs的根改成该子树重心，递归下去是按原树儿子所在子树的重心（每次找一遍），变成了子问题，可以处理与树形态没什么关联的问题发现siz每次减半，故深度log层；同时siz大小总和的复杂度是对的由于总是处理的整棵子树，而答案与子树遍历关系无关，所以一定是对的

1.定义在点分治的基础上加以变化，构造一颗支持快速修改的重构树，称之为点分树2.算法2.1.思路点分治的核心在于通过树的重心来划分联通块，减少合并层数，从而降低时间复杂度所以，我们可以按分治递归的顺序提出一颗树，易知树高至多为logn具体的说，对于每一个找到的重心，将上一次分治

linkofproblem。依旧是非常精妙的做法呢！问了神仙lca才知道怎么做了，目前网上是没有题解的，有的只是一份带注释的代码的英文题解。我的细节实现也是看了这份代码得以补足的。我们定义一些量：原树重心为rt，rt的某个儿子叫做son，son子树内的某个节点为x。首先考虑哪些连通块

最近学了点分治，觉得挺厉害的，准备写一下加深印象。树上的东西都很抽象，所以自然要用抽象的东西来做，就比如点分治，点分治的思路是在当前的子树中找重心，然后用重心做事情，为什么用重心，因为重心可以使得复杂度降到log级别，然后再在这个子树里找你要的东西就行了，因为是每次都会用子树做，所