自闭了，自闭选手不配拥有游记

题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单，给你一张图，然后图中不能选最大相邻点，最后最大的选中的点的权值

很容易想到 没有上司的舞会 这种树形 DP 题目，但是显然，这，并不是一棵树

根据题目可得，每一个人只会有一条出边，即，这张图中，一张节点个数为 $n$ 的联通块，会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边，删掉后就是树了

设这条边为 $u - v$ 的边，则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ，当反向边即可

题目链接: https://oj.woshiluo.site/problem/2055 / https://www.luogu.org/problemnew/show/P5323

我看到题目的一瞬间

我是在学 oi 还是在学物理？

然后我仔细思考了一下，这两个镜子来回反射，您这是要求极限？

然后我仔细思考了一下

设 $f_i$ 为从 $1$ 到 $i$ 的透光率，$g_i$ 为从 $i$ 到 $1$ 的反光率

题目链接: https://www.luogu.org/problemnew/show/P3809

后缀数组

后缀数组用于解决各种玄学字符串问题，准确来说，它是一种思想

基于后缀数组有很多好玩毒瘤的东西

目前已知的求后缀数组的方法有

• 倍增法 (本博客所讲述) -- $O(n \log(n))$
• DC3 -- $O(n)$
  • DC3 虽然从复杂度分析的角度而言比倍增快，但配合各种常数问题，在信息学竞赛中反而容易被卡……
• SA - IS 算法 -- $O(n)$
  • 可以参考这篇 Luogu 日报: https://www.luogu.org/blog/ShadowassIIXVIIIIV/on-hou-zhui-shuo-zu-sa-is-suan-fa

因为我太菜了，所以我就讲倍增求法

题目链接: https://www.luogu.org/problemnew/show/P3174

这应该是我第一次没看 sol 做紫题吧……

虽然个人感觉比大多数紫题简单许多

题目本质是要求最长链的，但是要求是带每个点周围点的

我们设每个点的点权是这个点的连接点个数减 1

然后求最长链

得出来的链的长度 +2 即为答案

可以理解为因为大多数点都有一条边要连出去防止重复计算而减一

但是这样链头链尾会没算上，所以加二