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

题目传送门先考虑换根操作，珂以直接对一个节点$x$分类讨论，因为这题只需要知道子树，那么只看子树的变动就好了。若根在初始关系中的$x$节点的上端，则$x$的子树没变换。若根是$x$，则$x$就是根。合理。若根是$x$中初始关系的子节点的子树，则$x$的子树就是

20241023模拟赛A.浇水考虑统计每个点被浇水了几次，容易用二维前缀和维护，最后如果这个点在对应颜色的矩阵里就扣除一个次数，最后有次数的就枯萎。B.藤养巴士赛时考虑树形dp，和树上差分解法殊途同归。设\(f_u\)表示，假设所有目标在\(u\)子树中的人都已经到了\(u\)子树中，

0.前言K-DTree是一种能够处理高维空间信息的数据结构，其在一些情况下能够代替CDQ分治以及树套树，较优秀地处理\(k\)维空间上的信息。参考资料：OI-wiki题单：\(\tt{Link}\)1.KDT的原理KDT的结构与BST类似，其每一个非叶子节点都具有超平面的作用，建树时会选择\(k\)维中某

CodeforcesRound987(Div.2)太好了是阳间场，我们有救了感觉脑子生锈了qwq，F题做不出来A分析知如果有\(i<j\)且\(a_i>a_j\)的情况出现则\(i\)和\(j\)一定至少改一个。所以答案即为\(n-cnt\)，\(cnt\)为众数个数。B发现一个数离自己原本的位置距离不会超过\(1\)，有

题目链接:最大子树和题目描述:小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：一株奇怪的花卉，上面共连有\(

思路：显然的，若不是叶子结点都应该至少遍历两次。于是两个相同访问之间就可能是一颗子树。更加具体的，如同\(s_l,\dots,s_k,\dots,s_r\)，使得\(s_l=s_k\)，那么就可以认为\(s[l,k]\)是\(s[l,r]\)的一颗子树，设区间\(s[l,r]\)的结构数量为\(f_{l,r}\)，那么根据乘法原理，当把\(

传送门给定一棵\(n\)个节点的树，根节点是\(1\)。这棵树的每一个叶节点都有一只小蚂蚁。每过\(1\)秒钟，可以选择让一些蚂蚁向父节点走一步。注意，两只蚂蚁不能同时在一个除去根节点的节点上。问这些蚂蚁最少用多少秒的时间，使得所有蚂蚁都走到根节点。根结点的各个子树独立，因

背景4.14打abc的时候一眼e题是换根模板，但是我不会，于是就来补档了。什么是树形dp/换根dp一种在树上的dp，一般用dfs进行状态转移。树形dp一般用儿子来更新父亲的答案。换根dp一般在第二次dfs时用父亲的答案转移到儿子去。引入经典树形dp例题：没有上司的舞

有一棵N个节点的树，节点i的权值为w[i]，可以剪掉其中一些枝，使得剩下的树上节点权值之和最大，求最大值。1<=N<=16000;-1E6<=w[i]<=1E6分析：题目要求至少要选1个节点，设dp[i]表示以i为根的子树，并且选择i的最大权值和。对于i的每个子节点，可以选或不选。#include<bits/stdc++.h>using

点分治思想回想序列分治的做法：递归统计两个区间，在统计跨两个区间的贡献对应到树上也类似：找一个分割点，统计子树的贡献，再统计跨子树的贡献由于路径都可以被某一级重心统计到，所以点分治长于做路径统计问题找树的中心树的中心：以它为根时的最大子树最小的点处理方式：开全局变量\(

多校A层冲刺NOIP2024模拟赛16T1四舍五入签到题注意到一个数是否会入上去只和其剩余系有关，即满足\(i\modj<\frac{1}{2}j\)，会入上去，考虑枚举j的倍数，其贡献就成了一个区间，差分即可。时间复杂度是调和级数的，为\(O(n\lnn)\)。T2填算符贪心，特殊性质显然将所有\(\&\)放

10.29多校联测30+35+0+0=65菜就多练T1:题意：给定一棵以1为根的树，从节点1出发，如果当前节点有儿子没走过，可以花费对应边权的时间走到儿子，否则不花费时间走回父结点。每个点带权值，要求最小化到达节点时间乘点权总和。解：非常明确的贪心，对于子树内部最优路径必然确定，只要考虑先

树与二叉树1.树的定义与相关概念树的示例：树的集合形式定义Tree=(K,R)元素集合：K={ki|0<=i<=n,n>=0,ki∈ElemType}（n为树中结点数，n=0则树为空，n>0则为非空树）对于一棵非空树，关系R满足下列条件：1.有且仅有一个结点没有前驱，称为根结点。2.处根结点外，其余每个结点有且仅有一个前

G.SakurakoandChefirGivenatreewith$n$verticesrootedatvertex$1$.WhilewalkingthroughitwithhercatChefir,Sakurakogotdistracted,andChefirranaway.TohelpSakurako,Kosukerecordedhis$q$guesses.Inthe$i$-thguess,heassumesthat

2024.10.23-25杂题P7323[WC2021]括号路径如果存在\((a,b,w)\),\((c,b,w)\)。那么\((a,c)\)就是一条合法路径。所以把\(a,c\)放入一个集合。然后合并新的的时候把\(w\)一样的合并了就行。最后统计每个"块"的数量，答案就是\(\sum_{i=1}^{n}C_{cnt_i}^{2}\)复杂度\(O(

文章目录题目介绍题解题目介绍题解最小深度：从根节点到最近叶子结点的最短路径上节点数量。分三种情况讨论即可：当前节点为空，则返回当前节点minDepth=0；当前节点左右子树都存在，则返回当前节点minDepth=左右子树最小深度的最小值+1；当前节点的左右子树其中一个不存

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

A答案为\(\sum\limits_{k\ge0}\sum\limits_{i=1}^n\sum\limits_{j=1}^n[a_i+b_j\ge10^k]\)。先把\(a,b\)排序，枚举\(k\)后双指针统计答案即可。时间复杂度\(O(n(\logn+\logV))\)。B若\(|a_i-a_j|=k\)就在它们之间连一条无向边。因为保证序列没有

虽然下蛋爷和红黑树都没做出来。description你有一颗有根树，有三种操作：对\(x\)子树内深度为\(k\)的所有点\(+s\)并求出最大值。对\(x\)子树内深度\(\lek\)的所有点\(+s\)并求出最大值。对\(x\)子树内所有点\(+s\)并求出最大值。规定：子树内，子树的根节点深

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

月考寄，遂学OI，whk中所以题目比较清新简单（[ABC301Ex]DifferenceofDistance无脑求最小生成树，如果权值\(+1\)的边\((u,v,t)\)不在\(x\toy\)路径上或者不是路径上的最大边，最小瓶颈路肯定不变否则想找一条权值为\(w\)非树边替换它，注意是最小生成树，\(w\get\)，而不变则

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

首先因为\(1\)点是可以一次性到多个点的，因此不需要考虑\(1\)点的情况，而是转而分析\(1\)的每个子树的情况，最后取\(\max\)。那么对于每个子树，就有每个节点每个时刻至多存在\(1\)个点的性质了。考虑如何去求解。首先一个贪心的想法是肯定是每个蚂蚁越早到一个点越好。于

感觉非常有深度，感觉过几天就又要忘了，所以我写个题解。P3806【模板】点分治1给定一棵有\(n\)个点的树，询问树上距离为\(k\)的点对是否存在。题意非常简单题意越短越毒瘤。大佬原文我们先想想点对有几种情况：第一种是经过根节点的路径；第二种是不经过根节点的路径；想第一