丢一发友链就跑 https://www.cnblogs.com/xuanyi/p/9010816.html qaq。

用 $f[i][0]$ 表示 $i$ 不选所能取到的最大值， $f[i][1]$ 表示选 $i$ 能取到的最大值。

假设当前节点为 $u$ ，孩子节点为 $v$ ，则：

• $f[u][0] = \sum max(f[v][0], f[v][1])$
• $f[u][1] = \sum f[v][0]$

关于判断是否有多种情况：我们无需存种树，只要存是否即可，用数组 $d$ 表示，则：

• 如果当前节点 $u$ 更新状态选中的来自 $v$ 的某个状态存在多种，那么 $u$ 的这个状态也存在多种。
• 如果 $u$ 节点的某个孩子 $v$ 满足 $f[v][0] == f[v][1]$ ，那么 $f[u][0]$ 存在多种。

膜蛤文化模板题 去他妈的NOI难度

从 $S$ 到 byx 的每个人连条容量为生命的边，从手气君的每个人到 $E$ 连条容量为生命的边；如果 byx 的这个人能打赢对方的某个人连一条容量为 $1$ 的边，$+1s$ 的话直接加到生命里，最后跑一遍最大流即可。

1. 单点修改 & 区间查询

   傻逼都会。

2. 区间修改 & 单点查询

   假设 $a$ 数组为我们当前维护的数组，定义 $b_i = a_i - a_{i - 1}$ ，则 $a_i = \sum_{j = 1}^{i}b_j$ 。用单点修改 & 区间查询的树状数组维护 $b$ ，修改区间 $l$ 到 $r$ 只需使 $b_{l-1} + value$ 且 $b_r - value$ ，查询 $a_i$ 只需求 $\sum_{j = 1}^{i}b_j$ 。

3. 区间修改 & 区间查询

   同 2 的假设下，求 $\sum_{i=l}^{r} a_i$ 即求 $\sum_{i=1}^{r} a_i - \sum_{i=1}^{l-1} a_i$ ，我们只需考虑如何求 $\sum_{i=1}^{k} a_i$ 。

   $\sum_{i=1}^{k} a_i = \sum_{i=1}^{k} \sum_{j=1}^{i} b_j = \sum_{i=1}^{k} b_i \times (i + 1 - x) = (k+1) \times \sum_{i=1}^{k} b_i + \sum_{i=1}^{k} (i \times b_i)$

   所以我们开两个树状数组，分别维护 $b_i$ 和 $i \times b_i$ 即可。

用 tarjan 遍历整个图，如果某个点是割点，当且仅当以下两种情况

1. 当前点是根节点，且当前节点出发独立的联通分量至少有两个
2. 当前点不是根节点，且当前节点出发的独立分量能回溯到的最早的点在当前节点之后

转换过来就是下面两个条件

1. u == root && child >= 2
2. u != root && low[v] >= dfn[u]

其他与 tarjan 算法无异。

本文不定时持续更新！

所有用到的资源可到 cloud.memset0.cn/分享/Windows10美化计划 中下载

成品效果如上

线性基是一种解决异或相关问题的算法。

感谢 mwh 与我分享关于线性基的理解，让我了解线性基。

概念

线性基理论上来说是一种贪心的思路。一般情况下，我们需要从（二进制）高位到低位贪心，然而这样可能会产生其他影响（例如当前数的选择与否会影响到之前已选择的数）。线性基就巧妙的解决了这个问题。

假设我们已经有了一个集合S，集合中有一数为P，现在我们需要插入X，则插入X和插入X ^ P是等价的，理性证明：

假设集合S中任意个数其中包含P的异或和的集合为S1，不包含P的为S2。则插入X后的S中任意数的异或和集合S' = X ^ S1 + X ^ S2；插入X ^ P后S中任意数的异或集合 S'' = (X ^ P) ^ S1 + (X ^ P) ^ S2 = X ^ (P ^ S1) + X ^ (P ^ S2) = X ^ S2 + X ^ S1。所以S' = S''插入X和插入X ^ P等价，证毕。

在 mwh 大佬的指引下，我最近学习了主席树。

思想

主席树是一种特殊的线段树，能够存储线段树的历史版本，我们称这种性质叫做可持久化。

主席树的可持久化通过这样来实现：我们每次修改单个节点，必然只会经过 $log_2n​$ 条“线段”，对于这些线段，我们都新开节点来存储。显然对于每一次修改操作，根节点都会被新建。那么我们只要存储下来每一次修改说对应的根节点即可。空间占用 $O(n log n)​$

具体思路可参考https://www.luogu.org/blog/LonecharmRiver/zhu-xi-shu中的图片。

关于模板题

我们要维护静态区间第 k 小。可以先把数组离散化，比如：

1
2
3

离散化前 4 1 1 2 8 9 4 4 3
离散化后 4 1 1 2 5 6 4 4 3
离散数组 1 2 3 4 8 9

我们根据离散数组作为所维护的区间。第 i 棵树存储[1, i]内各数值出现的次数。

最近的模拟赛出现了一道坑爹的数学题，正解是上一篇博文所讲的数学插值。然而高斯消元还是可以拿到 65 分的成绩，没办法，凭借着我对其原理的依稀记忆我只能考场上手推高斯消元。

原理

高斯消元其实是个很简单的东西，无非就小学奥数的难度罢了。按照小学奥数的加减消元和代入消元即可完成。模板题给了你 n 个的 n 元一次多项式求解。我们可以通过加减消元合并为 n - 1 个 n - 1 元的一次多项式（合并相邻两个）；于是，经过 n - 1 次合并我们就可以得到一个一元一次方程，可以很方便的得到解。我们再将解回代，即可解出方程。

这两天一直在信奥集训也没时间休息，基本上处于 早上七点不到起床 => 上午八点模拟赛 => 中午十一点半去吃饭 => 下午一点继续上课 => 下午五点去吃晚饭 => 晚饭吃完继续搞信奥 => 晚上九点多回家 => 继续刷题直到晚上十一点半 => 睡觉 的状态。也没有时间休息，今天好不容易暂时放假了，然而还是轻松不了，不过来水一篇博文的时间还是有的。

这段时间新学了很多算法（网络流乱搞 / 树上乱搞 / 数论乱搞 / 平衡树乱搞 等等），感觉自己学了很多知识。原本对于自己来说感觉很难很难的知识现在基本研究个几个小时也能解决了，比如 Splay （我还写了几篇有关她的博文）。当然本来感觉很充足的睡觉时间和休息时间现在也基本 disappear 了。谁说的期末考考完就轻松了给我站出来！

最近也新换了一处博客，毕竟新学了一些东西，觉得原来写的一些博文质量都很不高，打算重新开始。这当然也需要时间和过程，所以可能在很长的一段时间内我可能会一直维持两个博客都开着但只维护这里的状态。

我对博客的看法也发生了改变，也许当初是觉得新鲜，对此非常兴奋，浪费大量时间。不过现在心态也转变了，也觉得自己的博客是写给自己看的，其实别人看不看也没有什么关系，更何况本来看的人就屈指可数呢。