对一颗树上的信息统计，若能做到O(1)的加入数据和O(1)的删除数据，则可以使用dsu on tree 核心要点是树链，然后用一个数组统计，对于每个点每次先遍历所有轻儿子，每遍历一个轻儿子之后将该儿子子树数据删除，最后遍历重儿子，重儿子遍历出来后数据不删除，加上所有轻儿子子树的数据再加上该点本身的数据作为该点的数据。…

### 放宽限制 很经典的Trick，当题目的限制难以计算和维护时，考虑是否存在一种更平凡的维护条件，而能使得题目的限制在这种条件下自然称为最优解。 ### 差分贡献 形态1：类似 $a_i=k$ 提供 $k$ 贡献转化为对每个 $i$ ，使所有 $a_i \geq i $ 提供 $1$ 的贡献。 形态2：对每个最终结…

### 放宽限制 很经典的Trick，当题目的限制难以计算和维护时，考虑是否存在一种更平凡的维护条件，而能使得题目的限制在这种条件下自然称为最优解。 ### 差分贡献 形态1：类似 $a_i=k$ 提供 $k$ 贡献转化为对每个 $i$ ，使所有 $a_i \geq i $ 提供 $1$ 的贡献。 形态2：对每个最终结…

自己总结的有趣定理 > 定理：对于任意一张图 $G=(V,E)$ ，选取数个边集 $(E_1,E_2,E_3,...,E_k)$ 使其完全覆盖边集 $E$ 。对每个集合 $E_i$ 求最小生成树，得到边集 $E_{MST_{i}}$ 。再对 $E_{MST_{1}},E_{MST_{2}},E_{MST_{3}},..…

决策单调性表现为对于 $i>j$ 则 $f_i$ 的决策点 $p_i>p_j$ 。 决策单调性需要性质：相交优于包含，这条称作四边形不等式。 以最大贡献为例，即对于任意的 $a w(p_i,l)$ 说明该决策点完全不如 $i+1$ ，将其排除，否则在 $(l,r)$ 内二分一个 $i+1$ 优于 $p_i$ 的分界点…

定义：在一棵无根树中，每次删除最小的叶子并将叶子相连点编号加入序列。 性质：prufer序列与无根树一一对应 性质：大小为 $n$ 的无根树的数量有 $n^{n-2}$ 种，这同时也是完全图生成树的数量。 性质：每个结点在序列中出现的次数是其度数减一 建构：用一个指针维护目前最小的叶子，可以发现如果新出现的叶子比指针维…

~~*模拟赛遇到一个笨比线性基题但是忘了怎么求编号......最后因读入T掉来不及修改赛后20s过题，惨痛教训。*~~ 线性基是一组**极小的**用于表达一个数集异或空间的基底。其满足以下性质： 1.能由原数集异或得到的任意一个数，线性基中都有且仅有一个子集能表示它。 2.由1得，线性基中不存在一个数能被其它元素异或得…

Trick：放宽限制 很经典的Trick，当题目的限制难以计算和维护时，考虑是否存在一种更平凡的维护条件，而能使得题目的限制在这种条件下自然称为最优解。 思考如果只需要维护一个数列的重量，我们用线段树维护对于每个没出现的数，比它大的数有多少个，显然 $mex$ 对应的值会自然地成为其中的最大值。 考虑维护所有以 $r$…

经典差分思想的应用。 对每个 $a_i$ ,我们考虑每个位置 $pos$ 考虑贡献了多少次。由于考虑最后恰好移动到 $pos$ 的方案数较为难算，我们计算最后移动到 $\le pos$ 的方案数有多少种。 显然对每个 $a_i$ 最后可能移动到的位置只有 $q$ 种，分别是： $ \left\{ \begin{alig…

在文章《题解：CF2138D Antiamuny and Slider Movement》发表评论：

会T啊

很经典的线段树维护所有子区间的板子题。如果我没记错的话，这题应该就是我22年tg死磕T4的原因。 显然当一个区间的 $max-min=r-l$ 时这个区间满足“好区间”的限制，所以我们需要统计的是 $val=max-min-r+l=0$ 的区间的数量，由于维护 $val=x$ 的个数不好维护，但维护 $minval$…

最长公共子序列看起来很唬人，实际想一想就能知道最优方案一定是把最长公共子序列摆在从根下来连续的一根链上，这样能使每个 $0/1$ 被利用的程度最大。 考虑二分深度，接下来的问题变成了一个背包：每个深度的点必须染同一种颜色，要求最后恰好能有 $k$ 个点染成同一种颜色。 考虑到这个背包里所有的物品重量之和 $\leq n…

最长公共子序列看起来很唬人，实际想一想就能知道最优方案一定是把最长公共子序列摆在从根下来连续的一根链上，这样能使每个$0/1$被利用的程度最大。 考虑二分深度，接下来的问题变成了一个背包：每个深度的点必须染同一种颜色，要求最后恰好能有 $k$ 个点染成同一种颜色。 考虑到这个背包里所有的物品重量之和 $\leq n$…

### 对比 $c++$ **相似程度：大体相似** js中采用动态类型，变量与函数类型随其值/返回值自动改变，无需专门声明类型。 - [x] 句末分号（可选） - [ ] 严格缩进 - [x] 数组大小默认动态 - [x] 自动释放内存 在html中，使用 ``` event=funtion() ``` 来绑定事件和…

英文题面里有明确提到“每一局抓恰好一个人”，但中文题面没有，害我理解错了好久题面。

逆天题，又蠢又难写，赶紧换道题做吧。

在讨论《翻译 CF418D》回复：

这翻译的什么玩意儿。。。

在讨论《征询意见》回复：

洛谷这帖子改的什么nt样式，丑死了

在文章《浅谈信息论》发表评论：

bs好牛至！

在讨论《Generals AI对战平台正式发布》回复：

@[steam_powered](/user/210486) 他说的是带GUI的AI开发平台

在讨论《Generals AI对战平台正式发布》回复：

地图上一选择load map from generator就会报错

在讨论《Generals AI对战平台正式发布》回复：

根本找不到AI manager的界面啊

在讨论《mxqz Matrix-Tree 定理求最小生成树计数》回复：

orz zyf

在讨论《洛谷日报历年目录》回复：

@[Alex_Wei](/user/123294) 投稿[【学习笔记】拉插优化dp](https://lookcatbox.blog.luogu.org/lagyouhuadp)

在讨论《洛谷日报历年目录》回复：

@[kkksc03](/user/1) 投稿日报：https://lookcatbox.blog.luogu.org/lagyouhuadp

为什么别人的O(Tnm)能过我的过不了啊，枯了。 ```cpp #include #define N 100010 #define mod 10007 #define M 22 using namespace std; int p[N],vis[N],tot,g[N][M],C[N][M]; void add(int&…

```cpp #include #define N 1000010 #define K 55 #define mod 1000000007 #define int long long using namespace std; int read() { int res=0,f=1;char ch=getchar(); w…

在文章《DP专题-学习笔记：Slope Trick》发表评论：

不然你想想这题为啥是紫的

在文章《DP专题-学习笔记：Slope Trick》发表评论：

兄啊，你直接dp是nV的，就算n=3000也过不了吧（

在文章《DP专题-学习笔记：Slope Trick》发表评论：

短