CF1987E题解题意给定一棵大小为\(n\)的有根树，各点各有一点权\(a_i\)。每次操作可以选定一节点使其点权加一，求最小的操作数，使得任一节点满足其点权不大于其所有儿子的点权之和。\(n\le5000,0\lea_i\le10^9\)题解麻了，赛后十五分钟调出来，可惜为时已晚。读懂题之后

引入——最大权独立集问题：最大权独立集：对于一棵树，求出一个点集，这个点集里面的任意两个点都不相连。那么在所有这样的点集中，点权和最大的那个点集，就被成为最大权独立集。想要求出最大权独立集的点权和，我们只需要使用树上dp的方法即可实现设数组f[N][2]其中f[x][0]表示不选择

有操作的操作场，考场过了ABC（3/4）A.SugarWater题意：一个杯子，可以容纳\(F\)克糖水，一开始是空的。每次操作：加入\(100A\)克水加入\(100B\)克水加入\(C\)克糖加入\(D\)克糖每\(100\)克水最多溶解\(E\)克糖，求任意次操作后完全溶解的糖水中的最大含糖量，以

这道题目作为枚举子集的题目见识一下首先对于一个连通块，如果点权之和为\(0\)，那么我们算出MST显然就是最优解我们看一下数据范围，可能是考状态压缩我们把状态\(i\)设出来后，可以先尝试考虑某一个点，但是你发现这样不太好考虑，而且只考虑这一个点的话，那么这个点所加入的连通块的点权

分析首先发现此题的式子一看就不是很友好。所以尝试化简。原式：\(max(|a_u+a_v|,|a_u-a_v|)\)。分类讨论：当\(a_u>0,a_v>0\)时，显然有原式\(=a_u+a_v\)；当\(a_u>0,a_v<0\)时，\(|a_u-a_v|=|a_u+|a_v||\)，\(|a_u+a_v|=|a_u-|a_v||\)。肉

因为我记忆力不好，经常遇到之前做过的题一下子想不起来，所以打算基本上给每个比较有意思的题写题解，同时造福后代。这是werewolf，它是furry，很可爱题意：一张无向图，点有点权，每次询问从\(u\)到\(v\)的路径中，是否存在一条先走点权大于等于\(L\)，再走点权小于等于\(R\)的路径。思路

关于我在赛场上一题都没有切，后面自己推出来正解这件事~题面翻译给定一个长度为\(N\)的整数序列\(A=(A_1,A_2,\cdots,A_N)\)和另一个长度为\(N-1\)的整数序列\(P=(P_2,\cdots,P_N)\)。注意\(P\)的索引从\(2\)开始。对于每个\(i\)，保证\(1\leqP_i<i\)。现在您

915-F题目大意给定一棵\(n\)个节点的树，节点带权，设函数\(I(x,y)\)等于点\(x\)到点\(y\)的路径上最大的点权与最小的点权之差。求：\[\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)\]Solution令函数\(F(i,j)\)等于点\(x\)到点\(y\)的路径上最大的点权，函数\(G(i,j)\)等于点\(x\)到点\(y\)

诸位大佬把思路讲的很清晰了，我主要补充一下实现。思路考虑：如果一个询问的答案是肯定的，它对路径上所有点的要求。询问为abe。因为只有\(e\)点能量，所以能走到的最大高度只有\(h_a+e\)，没有最小高度。若路径上所有点的点权都在这个范围内，这个询问成立。问题转化成：\(a\)

洛谷题面感觉有点毒瘤，不过还是有些trick在的。题意翻译（复制于洛谷题面）：给定一个\(N\)个点\(M\)条无向边的图，图上每个点都有其颜色。求所有经过点权单调不降的路径中，出现的不同颜色的个数最多是多少。由于是单调不降的路径，所以可以点权大的点到点权小的点的路径对结果没

挺简单的知识点（？）概念首先Kruskal算法是用来求最小生成树的算法之一，其思想是贪心。而Kruskal重构树就是将整张图重建为二叉树。在跑Kruskal的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。首先新建\(n\)个集合，每个集合恰有一个节点，点权为\(0\)。每

Kruskal重构树一般用于求图上任意两点间距离的最值，距离为路径上边权最值。建树：将边权升序排序后，依次把点对加入树中，每次把两点当前所在的树根与一个新点连边，点权为原边权，然后新加的点成为树根。例如，对于以下最小生成树：它的Kruskal重构树为：性质：对于原图上的两点，它们的距离

今天学习了圆方树，并且做了一道和这道题很像的题，于是就又来做了一下这道题。题意给定一张不保证连通的无向图。求有多少个点对\((a,b,c)\)满足\(a\)到\(c\)的简单路径上经过了点\(b\)。思路显然圆方树。点双缩点过后构造一颗圆方树，然后考虑如何计算答案。圆方树有一个实

题目传送门前置芝士：缩点、拓扑排序。题目描述有向图\(G\)有\(N\)个点，\(M\)条边，点\(u\)的点权为\(A_u\)。若存在三元组\(a,b,c\)使得\(a\)至\(b\)有一条边，\(b\)至\(c\)有一条边，则连一条\(a\)至\(c\)的边。重复执行以上操作，直到不存在这样的三元组为止。

\[\text{NOIP模拟赛-2023.11.10}\]T1进步科学一棵以\(1\)为根的\(n\)个点的树，初始时所有点的点权都是\(0\)，每个点有期望的点权（\(0\)或\(1\)）。每次操作可以选择一个点\(i\)变化它的点权，这个操作效果会在一秒后传给它的父亲，在\(j\)秒后传给它的\(j\)级祖先。特别的，

把Kruskal的合并过程变成新增一个点，并把点权赋值为该边权，得到一颗树。这棵树有一些美妙的性质，比如当是最小生成树时，两点的lca的点权为它们所有路径中最大值最小的边权；反之，为它们所有路径中最小值最大的边权。还有，它是一个堆！！（欢呼这简直是太美妙啦~：)heihei你可以套好多好

考试笔记从暑假集训开始。质量不等。后面的笔记质量要高一些。2023.08.22T1T2一个很显然的思路是先预处理，把所有图形搜出来，并算出它们所占据的空间，然后对于每组询问做到\(O(1)\)查询（二维前缀和）。难点就在于如何去重相同的图形。T3这么喜欢出矩阵乘法吗。一眼\(O(n^3\l

题意有一棵有\(n\)个节点的树，第\(i\)个节点有点权\(a_i\)。定义\(g(x,y)\)为\(x\)到\(y\)的树上路径所经过的点的点权\(\gcd\)。对于每一个正整数\(k\in[1,2\times10^5]\)求出满足以下条件的\(x,y\)的对数:\(1\lex\ley\len\)\(g(x,y)=k\)\(1\len

洛谷传送门CF传送门模拟赛赛时做法。看到查询路径点权最小值，想到建重构树，满足重构树上\(\operatorname{LCA}(x,y)\)为原树上\(x\toy\)路径的点权最小值。建树方法可以参考CF1797FLiHuaandPath。于是问题变成了，维护一个点集，支持加点，查询给定点\(x\)到点集中所有

计算器、背包、代码都不能带进考场禁赛三年并全国通报B选项符合while语句弱类型编程语言指的是可以进行类型转换，可以参与各种类型变量的运算\[3\times60(秒)\times44.1\times1000(赫兹)\times16\div8(字节)\times2(声道数)\div1024\div1024\approx30MiB\]

【模板】普通平衡树&【模板】普通平衡树（数据加强版）考虑最简单的平衡树——Treap（Tree+heap），从它的名字上就可以看出它是树和堆结合的产物。那它究竟是怎么样呢？别着急，要研究它，必须研究它的基础版本——BinarySearchTree，二叉搜索树，简称BST。简单来说，它需要满足对于任意一点，它的左

破防场。全是诈骗提。但是很有可以学的东西！\(I.\)给定\(n\)个01?串，?可以替换为0或1。称替换完的串集合为该串的生成串。问所有\(n\)个串的生成串集合的并的大小。长度不同的串分开处理。对于长度\(\le20\)的串，暴力枚举生成串，map去重。对于长度\(>20\)的

首先发现一个性质，那就是每个点的点权是\(\logn\)级别的。因为假设要造出一个点权为\(i\)的点至少需要大小为\(mn_i\)的子树，那么显然有\(mn_i=\sum\limits_{j=0}^{i-1}mn_j+1\)，即\(mn_i=2^i\)。由于点权不是很大，因此我们很容易地往变换复合的角度思考。将整棵树进行轻重

U12讲笔记树链点权最值问题暴力：对于随机数据，单次查询平均复杂度\(O(\logn)\)目标：对于最差情况，单次查询复杂度\(O(\logn)\)倍增(\(\rmbinary\;lifting\)):预处理ST表（稀疏表）,\(\rmp[u][i]\)代表\(u\)的第\(2^i\)个祖先，\(\rmst[u][i]\)代表从\(u\)开始往上爬

集训模拟赛的题解应该都在CWOI杂题里。主要就是题目的记录？不太想写游记。简单题不会写。7.7考试，考得依托。7.8很趣味的数据结构！感觉很有集训那味啊，就是前面讲一会简单的东西然后突然上强度。gym100739E.LifeasaMonster还是挺简单。套路地把切比雪夫距离转成曼哈顿